/* 背包问题精选 */
最近在跟着*QI大神练习dp和背包，这周是背包专题，有兴趣的童鞋可以点进去看看，WU神说这周的题量很“和谐”╮(╯-╰)╭18道 。。。
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=42402#overview
不管怎样，还是很感谢WU神为我们找来这么好的题目，给我们带来这样的机会一起练题，学习，谢啦!!☆⌒(*＾-゜)v
怒刷了两个半天加一个中午，18道也只刷掉13道，觉得剩下的不太好做了，还是先总结一下，整理整理吧~ o(*￣▽￣*)ブ
A：POJ 3624
最为基础的01背包，和捡骨头一样的难度。不再细说，没学过01背包的，个人建议还是尽快去看看《背包九讲》吧~
直接上代码：
/*基础01背包 POJ 3624*/
#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<vector>#include<utility>#include<iostream>using namespace std;#define maxn 3402+5int n,m;class charm{public: int w,d;}a[maxn];int dp[12880+100];int main(){while(cin>>n>>m){memset(dp,0,sizeof(dp));for (int i = 0; i < n; i++){cin>>a[i].w>>a[i].d;}for (int i = 0; i < n; i++){for (int j = m; j >= a[i].w; j--)//注意01背包的循环顺序{dp[j] = max(dp[j],dp[j-a[i].w]+a[i].d);//转移方程}}printf("%d\n",dp[m]);}return 0;}
B：HDU 2546
应该是高端的饭卡问题。。
题意：购买物品是要确保自己的卡余额大于等于5，而且一旦大于等于5，就可以买任何价钱的物品（及时购买后余额为负），问经过合理的购买后能使卡内余额最小是多少？
思路：跟普通的01背包很相像，可是出现了一个条件：大于等于5块，可以买到任何价钱的物品。于是想到的思路是用五块钱（如果有5块钱）把最贵的物品（不用考虑最贵的商品是否大于5块钱，因为后来还要减掉）给买了，剩下的用01背包跑一遍，最后结果就是原先的钱数 - 减去5块剩下的钱能够买到的最多钱数 - 最贵的物品。
说不明白的看代码吧：
/*贪心+01背包 HDU 2546*/
#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<iostream>using namespace std;#define maxn 1000+5int n,m;int a[maxn];int dp[1000+100];int main(){while(cin>>n,n){memset(dp,0,sizeof(dp));for (int i = 0; i < n; i++){cin>>a[i];}cin>>m;if(m<5)cout<<m<<endl;else{sort(a,a+n);m -= 5;for (int i = 0; i < n-1; i++)//用m-5的钱 对前n-1个物品做背包{for (int j = m; j >= a[i]; j--){dp[j] = max(dp[j], dp[j-a[i]]+a[i]);}}//printf("%d\n",dp[5]);printf("%d\n",m+5-dp[m]-a[n-1]);}}return 0;}
C：UVA 624
题意：你有n分钟的磁带，有m种音乐（只选一次），分别有其播放的时间， 问怎样选取音乐，能把磁带最大程度的利用上（可能好多词都翻译错了，不过题意差不多。。。）
思路：用m种音乐 背包 可得不超过n的最长总音乐时间。那么怎样记录路径（具体选了哪几种音乐）呢？多用一个二维数组p[i][j]记录在第i首歌，磁带还剩j时，是否选择了这首歌。1表示选择，0表示未选。具体转移如下：
01背包转移方程：dp[i][j] = max(dp[i-1][j],dp[i-1][j-ci]+vi);
那么如果dp[i][j] == dp[i-1][j] -> 未在第i次选择的时候选择第j个。所以p[i][j] = 0;
如果dp[i][j] == dp[i-1][j-ci]+v[i] -> 在第i次选择的时候选择了第j个。所以p[i][j] = 1;
然后倒着推，就可以得到一种最佳方案选择的序列。（本题是special judge）
代码：
/* 01背包 + 记录路径 UVA 624*/
#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<iostream>using namespace std;#define maxn 100000+5int n,m;int a[25];int dp[maxn];bool p[25][maxn];int stack[25],top;int main(){while(scanf("%d %d",&n,&m)!=EOF){memset(dp,0,sizeof(dp));memset(p,0,sizeof(p));for (int i = 1; i <= m; i++)scanf("%d",&a[i]);for (int i = 1; i <= m; i++){for (int j = n; j >= a[i]; j--){if(dp[j] <= dp[j-a[i]]+a[i]){//判断过程dp[j] = dp[j-a[i]]+a[i];p[i][j] = 1;}else{p[i][j] = 0;}}}int i = m,v = n;top = 0;while(i > 0){//用栈存起来，就可以倒序输出if(p[i][v] == 1){stack[top++] = i;v -= a[i];}i--;}while(top>0){printf("%d ",a[stack[--top]]);}printf("sum:%d\n",dp[n]);}return 0;}
D：POJ 2184
考验思路的一道题（不是自己想出来的，╮(╯▽╰)╭）。
题意：给你n头奶牛，每头奶牛有两个价值，一个TS，一个TF（可正可负），让你选择奶牛，当选择的奶牛的TS，TF之和分别都非负时，TS+TF的最大值。
思路：往01背包上靠，可是这每个物品竟然有两个价值，难道是二维费用背包，可是又没有确定下来的背包的容量。纠结纠结又纠结之后，队友传来消息：能不能用其中一个价值当做物品花费，另一个价值当做真正的价值，这样做01背包，把背包容量不定，更新所有的0-100*2000，最后输出最大的那个结果。
整理起来就是用TS做物品花费，TF做物品价值，做01背包。但是要注意有负数的存在，如果用一维数组做背包，一定要注意第二重循环的顺序（因为背包的结果是用前一个状态转移来的，更新当前一层的数据时不能更改上一层的数据）。如果是二维数组，就不用纠结循环的顺序，不过要更新小于当前物品花费的数据。
代码：
/* 变形的01背包 POJ 2184*/
#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<iostream>using namespace std;#define maxn 2005#define INF 99999999#define LL long longint dp[maxn*100];int s[105],f[105];//以s为体积，f为价值，做01背包int main(){int n,i,j;while(scanf("%d",&n)!=EOF){for (i = 1; i <= n; i++){scanf("%d %d",&s[i],&f[i]);}for (i = 0; i <= 200000; i++){dp[i] = -INF;}dp[100000] = 0;for (i = 1; i <= n; i++){if(s[i] > 0){//TS正负的时候会有不同的循环顺序。for (j = 200000; j >= s[i]; j--)//一维时要注意循环顺序dp[j] = max(dp[j],dp[j-s[i]] + f[i]);}else{if(f[i]<=0)continue;for (j = 0; j <= 200000+s[i]; j++)//dp[j] = max(dp[j],dp[j-s[i]] + f[i]);}}int ans = 0;for (i = 100000; i <= 200000; i++){if(dp[i]>=0)ans = max(ans,dp[i]+i-100000);}printf("%d\n",ans);}return 0;}
E：HDU 2639
捡骨头2
题意：给你n个骨头的重量和对应骨头的价值，一个m重量的背包，求第k大的能装取的骨头价值。
思路：把问题从求最大的变成求第k大，所以不能只用一维的dp[j]表示最大值了，用dp[j][k]表示在用j的容量能得到的第k大价值。更新的时候就用O(2*k)的方法更新就可以了。
注意：第k大的定义，是把不同方案得到的相同价值当做一个结果，还是不同方案的结果不同。本题“NOTICE that,we considerate two ways that get the same value of bones are the same.”表明了是第一种。
代码：
/* 01背包的第k优方案 HDU 2639*/
#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<iostream>using namespace std;#define maxn 1000+5int n,m,k;int dp[maxn][65];int c[105],v[105];void Insert(int r[],int x){int i;for (i = 0; i < 2*k; i++)if(r[i] == x)return;if(x > r[2*k-1])r[2*k-1] = x;else return ;for (i = 2*k - 2; i >= 0; i--){if(r[i] < x)r[i+1] = r[i];else{r[i+1] = x;break;}}if(i == -1)r[0] = x;}int main(){int t,i,j,a,b;scanf("%d",&t);while(t--){memset(dp,0,sizeof(dp));scanf("%d %d %d",&n,&m,&k);for(i = 0;i<n;i++)scanf("%d",&v[i]);for(i = 0;i<n;i++)scanf("%d",&c[i]);for (i = 0; i < n; i++)for (j = m; j >= c[i]; j--)for (int p = 0; p < k; p++){a = dp[j][p];Insert(dp[j],a);a = dp[j-c[i]][p] + v[i];Insert(dp[j],a);}printf("%d\n",dp[m][k-1]);}return 0;}
F：POJ 2923
在WU神的提点下，1A了，o(*￣▽￣*)ゞ
题意：给n（n<=10）个家具的体积，给你两辆车，有各自的最大容量a,b. 问最少多少趟能够将这些家具从一个地方移到另一个地方。
思路：由于 n很小，所以想到用状态压缩（自己也想到了，没敢写╮(╯▽╰)╭，后来咬牙写了，也就A掉了o(*￣▽￣*)o ）先预处理把两辆车可以一趟运送的物品状态。
然后把每个状态当做物品，做背包就行啦，注意这个背包的物品 之间可能有重叠，所以要另开一个数组s，用来存放上次的状态，判断一下前后两个状态是否有重叠（s[j-c[i]]&State[i] ?= 0)
代码：
/* 状态压缩 + 背包 */
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int State[2500],c[2500],f[15],n,a,b,ind;int dp[1005],s[2500];bool judge(int s,int sum){//01背包判断 两车能否装下memset(dp,0,sizeof(dp));for (int i = 0; i < n; i++){if((1<<i) & s){for (int j = a; j >= f[i]; j--){dp[j] = max(dp[j],dp[j-f[i]]+f[i]);}}}if(sum-dp[a] > b)return 0;return 1;}void init(){//预处理ind = 0;int sum = 0,j;for (int i = 1; i < (1<<n); i++){sum = 0;j = 0;while(j < n){if((1<<j) & i)sum += f[j];j++;}if(sum > a+b)continue;if(judge(i,sum)){c[ind] = sum;State[ind++] = i;}}}int main(){int t;scanf("%d",&t);int cas = 1;while(t--){scanf("%d%d%d",&n,&a,&b);int sum = 0;for (int i = 0; i < n; i++){scanf("%d",&f[i]);sum += f[i];}init();for (int i = 0; i < 1005; i++){dp[i] = 0x3f3f3f3f;}memset(s,0,sizeof(s));dp[0] = 0;for (int i = 0; i < ind; i++){for (int j = sum; j >= c[i]; j--){if((s[j-c[i]] & State[i]) == 0){//判断状态是否有重叠if(dp[j] > dp[j-c[i]]+1){dp[j] = dp[j-c[i]] + 1;s[j] = s[j-c[i]] | State[i];}}}}printf("Scenario #%d:\n",cas++);printf("%d\n\n",dp[sum]);}return 0;}
G：HDU 3466
题意：还是买东西，n个物品，m块钱，n个物品的价钱p和价值v。不过有所不同的是 每个物品还有一个 预备价钱q>=p，意思是要买这一件物品，只有你手里的钱数大于q了，才可以买这个物品。
思路：下意识觉得好简单啊。。可事实总是打击人，只改了背包的第二重循环之后，发现连第二个测试用例都过不了（输出9）。但是把第二组用例的物品输入顺序变一下，就能得到正确结果。这就让人费解了啊，，，为啥啊。。。仔细和队友讨论了之后，发现对于前两个物品5,10,5和3,5,6。
如果程序只改了这一段：
for (int i = 0; i < N; i++)
{
for (int j = M; j >= a[i].q/*把a[i].p改掉*/; j--)
{
dp[j] = max(dp[j],dp[j-a[i].p]+a[i].v);
}
}
先处理第一个物品5,10,5，我手里的钱是10,10>=10了，所以我可以买这件物品，就把dp[10]更新为了5；
再处理第二件物品3,5,6,时 j从10减到5的过程中，只能得到dp[10] = 6>5，更新dp[10]=6.
但是事实呢，是这样的：我手里有10块钱，达到了第一件物品的预备价格，买到第一件物品，花去5块，还剩10-5=5块，得到了5的价值
然后5块钱也达到了第二件物品的预备价格，买到第二件物品，花去5块，手里5-5没钱了，可是可以得到5+6=11的价值。
可是为何dp转移的时候，做不到这一点呢？？？
因为第一次只更新了dp[10]，然而第二次想到dp[10]的时候，必须保证 j-a[i].p >=10 所以j要大于等于13，才能重新更新到。（可以尝试一下，程序按上面的改，把钱数改成13，只用前两个物品，就可以得到11的结果。）
再考虑：怎样可以避免出现前面更新的时候更新不全？？？
想最基础的01背包，不在乎物品的输入顺序，这个多了一个预备价格，考虑是不是跟物品做背包的顺序有关。。。（好像有点结果论的意思，我也说不太明白╮(￣▽￣")╭ ）。
因为要想先更新第1件物品，再想更新到第二件物品时，需要的背包容量是10+3=13，第一件的预备价格+第二件的真实价格。
如果把顺序互换，要更新全，就需要5+5=10，第二件的预备价格+第一件的真实价格。
所以想到 把原先的物品x,y 按 前一件的预备价格 + 后一件真实价格排序，然后再做正常的背包o(*￣▽￣*)ゞ
代码：
/* 变形01背包 结果与物品顺序有关 HDU 3466 */
#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<iostream>using namespace std;#define maxn 2005#define INF 99999999#define LL long longint dp[5050];int N,M;struct node{int p,q,v;}a[550];int cmp(node x,node y){return (x.q+y.p) < (y.q+x.p);//重点啊。。}int main(){while(scanf("%d%d",&N,&M)!=EOF){memset(dp,0,sizeof(dp));for (int i = 0; i < N; i++)scanf("%d%d%d",&a[i].p,&a[i].q,&a[i].v);sort(a,a+N,cmp);for (int i = 0; i < N; i++){for (int j = M; j >= a[i].q/*把a[i].p改掉*/; j--){dp[j] = max(dp[j],dp[j-a[i].p]+a[i].v);}}printf("%d\n",dp[M]);}return 0;}
/* 求最优方案的个数（二维） HDU 2126 */
#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<iostream>using namespace std;#define maxn 550#define INF 99999999#define LL long long//求最优方案的个数int dp[35][maxn];//dp[i][j] i个物品，花j元，能得到dp个物品。int g[35][maxn];int a[maxn]={0};//花费为a，价值是1int n,m;int main(){int t;scanf("%d",&t);while(t--){memset(dp,0,sizeof(dp));memset(g,0,sizeof(g));//for(int i = 0;i<505;i++)g[0][i] = 1;scanf("%d%d",&n,&m);for (int i = 1; i <= n; i++)scanf("%d",&a[i]);for (int i = 1; i <= n; i++){for (int j = 0; j < a[i]; j++){dp[i][j] = dp[i-1][j];g[i][j] = g[i-1][j];}for (int j = a[i]; j <= m; j++){dp[i][j] = max (dp[i-1][j],dp[i-1][j-a[i]]+1);if(dp[i-1][j] < dp[i-1][j-a[i]]+1 ){if(g[i-1][j-a[i]] == 0)g[i][j] = 1;else g[i][j] = g[i-1][j-a[i]];}else if(dp[i-1][j] == dp[i-1][j-a[i]]+1 ){if(g[i-1][j-a[i]] == 0)g[i][j] = g[i-1][j]+1;else g[i][j] = g[i-1][j]+g[i-1][j-a[i]];}else g[i][j] = g[i-1][j];}}if(dp[n][m] == 0)printf("Sorry, you can't buy anything.\n");elseprintf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n",g[n][m],dp[n][m]);}return 0;}
/* 求最优方案的个数（一维） */
#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<iostream>using namespace std;#define maxn 550#define INF 99999999#define LL long long//求最优方案的个数int dp[maxn];//dp[i][j] i个物品，花j元，能得到dp个物品。int g[maxn];int a[maxn]={0};//花费为a，价值是1int n,m;int main(){int t;scanf("%d",&t);while(t--){memset(dp,0,sizeof(dp));memset(g,0,sizeof(g));scanf("%d%d",&n,&m);for (int i = 1; i <= n; i++)scanf("%d",&a[i]);for (int i = 1; i <= n; i++)for (int j = m; j >= a[i]; j--){if(dp[j] < dp[j-a[i]]+1 ){dp[j] = dp[j-a[i]]+1;if(g[j-a[i]] == 0)g[j] = 1;else g[j] = g[j-a[i]];}else if(dp[j] == dp[j-a[i]]+1 ){if(g[j-a[i]] == 0)g[j] = g[j]+1;else g[j] = g[j]+g[j-a[i]];}}if(dp[m] == 0)printf("Sorry, you can't buy anything.\n");elseprintf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n",g[m],dp[m]);}return 0;}
I：HDU 4281 不会做。。
J：UVA 674 题意：给你n元钱，五种硬币，问最多有几种方式来change。 思路：直接背包就行了。 代码：
/* UVA 674 */
#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<iostream>using namespace std;#define maxn 6050#define INF 99999999#define LL long long#define mod 100000000000000000LL dp[7500];int a[6] = {0,1,5,10,25,50};int n;int main(){memset(dp,0,sizeof(dp));dp[0] = 1;for (int i = 1; i <= 5; i++)for (int j = a[i]; j <= 7489; j++)dp[j] += dp[j-a[i]];while(scanf("%d",&n)!=EOF){printf("%lld\n",dp[n]);}return 0;}
K：UVA 147 题意：和上一题几乎一模一样。。 注意：化小数为整数，输出形式。 代码： //二维
/* UVA 147 */
#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<iostream>using namespace std;#define maxn 6050#define INF 99999999#define LL long long#define mod 100000000000000000LL dp[12][maxn];int x,y;int n;int a[12] = {0,1,2,4,10,20,40,100,200,400,1000,2000};//a[i]*5cint main(){while(scanf("%d.%d",&x,&y)!=EOF){if(x==0 && y==0)break;n = x*20 + y/5;memset(dp,0,sizeof(dp));for(int i = 0;i<11;i++)dp[i][0] = 1;for (int i = 1; i <= 11; i++){for (int j = 0; j < a[i]; j++){dp[i][j] = dp[i-1][j];}for (int j = a[i]; j <= n; j++){dp[i][j] = dp[i-1][j] + dp[i][j-a[i]];}}printf("%3d.%02d%17lld\n",x,y,dp[11][n]);}return 0;}
//一维
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
#define maxn 6050
#define INF 99999999
#define LL long long
#define mod 100000000000000000
LL dp[maxn];
int x,y;
int n;
int a[12] = {0,1,2,4,10,20,40,100,200,400,1000,2000};//a[i]*5c
int main(){
memset(dp,0,sizeof(dp));
dp[0] = 1;
for (int i = 1; i <= 11; i++)
{
for (int j = a[i]; j <= 6000; j++)
{
dp[j] += dp[j-a[i]];
}
}
while(scanf("%d.%d",&x,&y)!=EOF){
if(x==0 && y==0)break;
n = x*20 + y/5;
printf("%3d.%02d%17lld\n",x,y,dp[n]);
}
return 0;
}
L：POJ 3181 题意：和上两题一样。 注意：结果会超long long ，用高精度，事实证明只需要用两位来存，一个存高位，一个存低位，低位设为17位就够了。 代码：
/* POJ 3181 */
#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<iostream>using namespace std;#define maxn 1005#define INF 99999999#define LL long long#define mod 100000000000000000LL dp[maxn][maxn][2];int N,K;int main(){while(scanf("%d%d",&N,&K)!=EOF){memset(dp,0,sizeof(dp));for (int i = 0; i < maxn; i++)dp[i][0][0] = 1;for (int i = 1; i <= K; i++){for (int j = 0; j < i; j++){dp[i][j][0] = dp[i-1][j][0];dp[i][j][1] = dp[i-1][j][1];}for (int j = i; j <= N; j++){dp[i][j][0] = dp[i-1][j][0] + dp[i][j-i][0];dp[i][j][1] = dp[i-1][j][1] + dp[i][j-i][1];dp[i][j][1] += dp[i][j][0]/mod;dp[i][j][0] %= mod;}}if(dp[K][N][1])printf("%lld%017lld\n",dp[K][N][1],dp[K][N][0]);else printf("%lld\n",dp[K][N][0]);}return 0;}
M：POJ 1787 多重背包 题意：给你四种硬币，各有ci个，让你去买价钱是n的coffee，要求用最多的硬币去买，输出最多用的硬币方案（special judge）。 分析：这次不是01背包了，有物品的个数的限制，就是多重背包，多重背包的常用解决方式就是将其化为01背包。比较好的方法是 用二进制分解。 比如5个物品，可以分成1,2,2，三个01的物品，每个物品只选一个，可以*组合成0,1,2,3,4,5的方案，所以二者是等价的，再用01背包的方法处理就简单多了。 再有就是输出方案，可以参考C题的处理方法。 代码：
/* POJ 1787 */
#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<iostream>using namespace std;#define maxn 10005#define INF 99999999#define LL long long//需要装满的多重背包+输出方案int n,m;struct node{int c,v;}p[200];int dp[maxn];bool v[200][maxn];int q[6]={0,1,5,10,25};int bin[16]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384};void partition(int x,int j){int i = 0;while(x){if(x >= bin[i]){p[n].c = q[j]*bin[i];p[n++].v = bin[i];x -= bin[i];i++;}else{p[n].c = q[j] * x;p[n++].v = x;break;}}}void binary_partition(int a,int b,int c,int d){n = 0;partition(a,1);partition(b,2);partition(c,3);partition(d,4);}void ZeroOnePack(){for (int i = 0; i < maxn; i++)dp[i] = -INF;memset(v,0,sizeof(v));dp[0] = 0;for (int i = 0; i < n; i++)//for (int j = p[i].c; j <= m; j++)for(int j = m;j>=p[i].c;j--)if(dp[j] <= dp[j-p[i].c]+p[i].v){dp[j] = dp[j-p[i].c]+p[i].v;v[i][j] = 1;}if(dp[m] == -INF){printf("Charlie cannot buy coffee.\n");return ;}int stack[200],top = 0;int i = n-1,j = m;while(i >= 0){if(v[i][j] == 1){stack[top++] = i;j -= p[i].c;}i--;}if(j != 0){printf("Charlie cannot buy coffee.\n");return ;}int a=0,b=0,c=0,d=0,tmp,tt;while(top>0){tmp = stack[--top];tt = p[tmp].c/p[tmp].v;if(tt == 1)a += p[tmp].v;else if(tt == 5)b+= p[tmp].v;else if(tt == 10)c+= p[tmp].v;else if(tt == 25)d+= p[tmp].v;}printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n",a,b,c,d);}int main(){int a,b,c,d;while(~scanf("%d%d%d%d%d",&m,&a,&b,&c,&d)){if((m|a|b|c|d) == 0)break;if(m > (a+b*5+c*10+d*25)){printf("Charlie cannot buy coffee.\n");continue;}binary_partition(a,b,c,d);#if 0printf("%d\n",n);for (int i = 0; i < n; i++)printf("%d %d\n",p[i].c,p[i].v);#endifZeroOnePack();}//system("pause");return 0;}
N：POJ 3260 不会做啊。。
O：POJ 2063 题意：给你n元钱，和kinds种债券，买每个债券，每年有分红，问你year年后 最多本息加一起 有多少钱。 分析：不断的做01背包就行了。 注意：The value of a bond is always a multiple of $1 000. 可以把钱数除以1000，减少内存。The interest of a bond is never more than 10% of its value. 可以控制最大钱数。 代码：
/* POJ 2063 */
#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<iostream>using namespace std;#define maxn 10005#define INF 99999999#define LL long longint c[15],v[15];int dp[100000];// 1.1^40 = 45.26int main(){int t,n,n1,year,kinds,now;scanf("%d",&t);while(t--){now = 0;scanf("%d %d",&n,&year);n1 = n/1000;scanf("%d",&kinds);for (int i = 0; i < kinds; i++)scanf("%d %d",&c[i],&v[i]);while(now < year){memset(dp,0,sizeof(dp));for (int i = 0; i < kinds; i++){for (int j = c[i]/1000; j <= n1; j++){dp[j] = max(dp[j],dp[j-c[i]/1000]+v[i]);}}n += dp[n1];n1 = n/1000;now++;}printf("%d\n",n);}return 0;}
好啦，我现在能做的都写上来啦，有什么问题可以一起讨论哈Σ(⊙▽⊙"a...