饼干
原题链接：
https://www.acwing.com/problem/content/279/
题目描述
圣诞老人共有M个饼干，准备全部分给N个孩子。
每个孩子有一个贪婪度，第 i 个孩子的贪婪度为 g[i]。
如果有 a[i] 个孩子拿到的饼干数比第 i 个孩子多，那么第 i 个孩子会产生 g[i]*a[i]的怨气。
给定N、M和序列g，圣诞老人请你帮他安排一种分配方式，使得每个孩子至少分到一块饼干，并且所有孩子的怨气总和最小。
输入格式
第一行包含两个整数N,M。
第二行包含N个整数表示g1~gN。
输出格式
第一行一个整数表示最小怨气总和。
第二行N个空格隔开的整数表示每个孩子分到的饼干数，若有多种方案，输出任意一种均可。
数据范围
1≤N≤30,
N≤M≤5000,
1≤gi≤107
输入样例：
3 20
1 2 3
输出样例：
2
2 9 9
题解
题目求每个小孩的a[i] * g[i]相加最小。运用排序不等式可知g[i]最小乘以a[i]最大相加可以得到总和最小。
#include "iostream"
#include "cstring"
#include "algorithm"
using namespace std;
const int N = 35, M = 5010;
typedef pair<int, int> PII;
int n, m;
int f[N][M];
PII g[N];
int s[N];
int ans[N];
int main(){
cin>>n>>m;
for(int i = 1; i <= n; i++){
cin >> g[i].first;
g[i].second = i;
}
sort(g + 1, g + n + 1);
reverse(g + 1, g + n + 1);
for(int i = 1; i <= n; i++) s[i] = s[i-1] + g[i].first;
memset(f, 0x3f3f, sizeof(f));
f[0][0] = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(j < i) continue;
f[i][j] = f[i][j-i]; //有0个1
for(int k = 1; k <= i; k++){
f[i][j] = min(f[i][j], f[i-k][j-k] + (s[i] - s[i - k])*(i - k));
}
}
}
cout << f[n][m] <<endl;
int i = n, j = m, h = 0;
while(i){
if(f[i][j] == f[i][j-i]) j -= i, h++;
else{
for(int k = 1; k <= i; k++){
if(f[i][j] == f[i-k][j-k] + (s[i] - s[i - k])*(i - k)){
for(int u = i - k + 1; u <= i; u++) ans[g[u].second] = 1 + h;
i -= k;
j -= k;
break;
}
}
}
}
for(int i = 1; i <= n; i++) cout << ans[i] << " ";
cout << endl;
return 0;
}
划分数
题目描述
有n个无区别的物品，将他们划分成不超过m组，求出划分方法数模M的余数。
1 <= m <= n <= 1000;
2 <= M <= 10000;
Input
输入 n,m,M分别代表n个物品、m个组、对M取模。
Output
输出划分方法数对M取模的余数。
题解
首先设dp[i][j]代表的是j的i划分。这里需要分两种情况进行讨论：
1.j<i：也就是j不够分为i个划分，这时候只能在i当前位置填0，所以就等于dp[i-1][j]的总数了。
2.j>=i：也就是j够分为i个划分，这里也需要分两种情况进行讨论。
-这时候第i个位置填0，所以需要加上dp[i-1][j]的总数
然而为了保证满足i个划分结构，可以先放i个1，这时候就是1,1,1…1保证有i个，然后再加上dp[i][j – i]个划分的总数即可。
#include <iostream>
const int N = 1010;
int f[N][N];
int main
{
int n, m, M;
cin >> n >> m >> M;
f[0][0] = 1;
for(int i = 1;i <= m;i++)
{
for(int j = 0;j <= n;j++)
{
// 如果当前分数大于i
if(j >= i)
{
f[i][j] = (f[i - 1][j] + f[i][j - i]) % M;
}
else
{
dp[i][j] = dp[i - 1][j];
}
}
}
cout << f[n][m] << endl;
}
}
参考