5105 Cookies 0x50「动态规划」例题
描述
圣诞老人共有M个饼干,准备全部分给N个孩子。每个孩子有一个贪婪度,第 i 个孩子的贪婪度为 g[i]。如果有 a[i] 个孩子拿到的饼干数比第 i 个孩子多,那么第 i 个孩子会产生 g[i]*a[i]的怨气。给定N、M和序列g,圣诞老人请你帮他安排一种分配方式,使得每个孩子至少分到一块饼干,并且所有孩子的怨气总和最小。1≤N≤30, N≤M≤5000, 1<=gi<=10^7。
输入格式
第一行两个整数N,M,第二行N个整数g1~gN。
输出格式
第一行一个整数表示答案,第二行N个整数表示每个孩子分到的饼干数。本题有SPJ,若有多种方案,输出任意一种均可。
样例输入
样例输入1 3 20 1 2 3 样例输入2 4 9 2 1 5 8
样例输出
样例输出1 2 2 9 9 样例输出2 7 2 1 3 3
来源
ITMO
本题校验器(SPJ)
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; //一些定义 const int ACCEPT = 0; const int WRONG_ANSWER = 1; //fstd 标准输出 fout 选手输出 fin 标准输入 FILE *fstd,*fout,*fin; int n, m, ans, val, c[32], g[32]; //执行比较操作。 bool DoCompare(){ fscanf(fin, "%d%d", &n, &m); for (int i = 1; i <= n; i++) fscanf(fin, "%d", &g[i]); fscanf(fstd, "%d", &ans); fscanf(fout, "%d", &val); // 答案不对 if (ans != val) return false; for (int i = 1; i <= n; i++) { fscanf(fout, "%d", &c[i]); // 每个孩子分到正整数块饼干 if (c[i] <= 0) return false; m -= c[i]; } // 饼干没有分完 if (m) return false; // 检查方案的怨气值是否等于输出的值 for (int i = 1; i <= n; i++) { int cnt = 0; for (int j = 1; j <= n; j++) if (c[j] > c[i]) cnt++; val -= cnt * g[i]; } return val == 0; } int main(int argc, char* argv[]) { if(argc!=4){ printf("参数不足 %d",argc); return -1; } //打开文件 if(NULL==(fstd=fopen(argv[1],"r"))){ return -1; } if(NULL==(fout=fopen(argv[2],"r"))){ return -1; } if(NULL==(fin=fopen(argv[3],"r"))){ return -1; } if(DoCompare()){ return ACCEPT; }else{ return WRONG_ANSWER; } }