给出一个 s ，然后给出 n 组邮票，问那一组可以凑出最大连续邮资。
对每一组邮票，求出当邮资为i时需要邮票数的最小值 d [ i ] ，边界为 d [ 0 ] = 0 、 d [ i ] > s 时break。类似于背包问题的求法，具体方法见代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1010;
int d[maxn],ans[20],num[20],a[20][20];
int main(){
int s;
while(~scanf("%d",&s)&&s){
int n;scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&num[i]);
for(int j=1;j<=num[i];++j) scanf("%d",&a[i][j]);
memset(d,0x3f,sizeof(d));
d[0]=0;
for(int j=1;j<maxn;++j){
for(int k=1;k<=num[i]&&j-a[i][k]>=0;++k)
d[j]=min(d[j],d[j-a[i][k]]+1);
if(d[j]>s){ans[i]=j-1;break;}
}
}
int best=-1,pos=0;
for(int i=1;i<=n;++i){
if(ans[i]>best) best=ans[i],pos=i;
else if(ans[i]==best){
if(num[i]<num[pos]) pos=i;
else if(num[i]==num[pos]){
bool ok=false;
for(int j=num[i];j>0;--j)
if(a[i][j]!=a[pos][j]){
ok=a[i][j]<a[pos][j];
break;
}
if(ok) pos=i;
}
}
}
printf("max coverage =%4d :",ans[pos]);
for(int i=1;i<=num[pos];i++)
printf("%3d",a[pos][i]);
printf("\n");
}
return 0;
}
|
** 本文迁移自我的CSDN博客，格式可能有所偏差。 **