http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1520
DP题。
这题的意思就是找一个最接近M的解,然后将其余部分与L对比。
由于,M,L均小于1000,且n<M+L < 2000 , 所以直接用数组不会有任何问题。
不过,我在做的时候偷懒了,在DP以及输出结果的时候,用了一些低效率的做法
#include <cstdio>
#include <algorithm>
using namespace std;
int c[1001];
int p[2001];
int s[2001];
int sum;
int main(){
int M,L,n,v;
while(scanf("%d%d",&M,&L) == 2 ){
if(M == 0 && L == 0)
break;
sum =0;
for(int i=0;i<=M;i++) c[i] = 0;
c[0] = 1;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&v);
p[i] = v;
sum += v;
for(int j=M-v;j>=0;j--)if(c[j] && c[j+v] == 0) c[j+v] = i;
//printf("\n");
}
for(v = M;v>0 && c[v] == 0;v--);
if(sum - v > L){
printf("Impossible to distribute\n");
}else{
int i=0;
//p[s[v]]
while(v>0){
s[i++] = c[v];
v = v - p[c[v]];
}
sort(s,s+i);
printf("%d",i);
for(int j=0;j<i;j++)
printf(" %d",s[j]);
printf("\n");
}
}
return 0;
}
分享到:
相关推荐
zju1001--1399的数据。全是.in和.out文件。
这个是浙江大学操作系统课程讲义,此部分为第2章,配套教材为操作系统的恐龙书
zju超强代码,大概有一半的题目吧,从别人那里弄的
zju电机学作业.pdf
zju 1025 Wooden Sticks http://acm.zju.edu.cn/show_problem.php?pid=1025
zju部分 解题报告zju部分 解题报告
cpp codes for zju.edu.cn problems
acm zju 额度cnacm zju 额度cnacm zju 额度cnacm zju 额度cnacm zju 额度cn
acm 新手必备 浙大 解答 代码库 zoj zju
zju 1048 Financial Managementhttp://acm.zju.edu.cn/show_problem.php?pid=1048
ZJU/zoj 题库上的部分题源码 本人博客: hi.baidu.com/xiaoxianxi_acm
zoj700代码,供acm爱好者研究学习,但请注意,切勿上交。
2、课后作业题6.8 3、Minimax 给一个只有叶子节点值的图 叉掉α-β pruning 4、贝叶斯网络 5、Markov Network 给一个Mark
zju 1642 Match for Bonus DP,滚存??zju 1642 Match for Bonus DP,滚存??zju 1642 Match for Bonus DP,滚存??zju 1642 Match for Bonus DP,滚存??zju 1642 Match for Bonus DP,滚存??
zju题目与解答集合,学习ACM编程不可多得的好东西。
1520 Duty Free Shop 简单题 1524 Supermarket 简单题 1301 The New Villa 简单题 1303 Jury Compromise 其实不是很难,但是很容易错,555…… 1345 Best Deal 简单题,但是也很容易错……555…… 1360 ...
zju动态规划试题选集 ,有ZOJ所有的动态规划题及其代码,很好的!!!
ZJU_V1.2.10.apk
zju 3406题 题目打包 http://hi.baidu.com/leokan/blog/item/baa1e6c48c9af5af8326acfa.html