zju 1520 Duty Free Shop
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1520
DP問題.
この問題の意味は、Mに最も近い解を探して、残りの部分をLと比較することです.
M,Lはいずれも1000未満であり,n
でも、私はサボって、DPと出力の结果の时、いくつかの非効率的な方法を使いました
DP問題.
この問題の意味は、Mに最も近い解を探して、残りの部分をLと比較することです.
M,Lはいずれも1000未満であり,n
でも、私はサボって、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("
");
}
for(v = M;v>0 && c[v] == 0;v--);
if(sum - v > L){
printf("Impossible to distribute
");
}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("
");
}
}
return 0;
}