度度熊与邪恶大魔王
度度熊为了拯救可爱的公主，于是与邪恶大魔王战斗起来。
邪恶大魔王的麾下有n个怪兽，每个怪兽有a[i]的生命值，以及b[i]的防御力。
度度熊一共拥有m种攻击方式，第i种攻击方式，需要消耗k[i]的晶石，造成p[i]点伤害。
当然，如果度度熊使用第i个技能打在第j个怪兽上面的话，会使得第j个怪兽的生命值减少p[i]-b[j]，当然如果伤害小于防御，那么攻击就不会奏效。
如果怪兽的生命值降为0或以下，那么怪兽就会被消灭。
当然每个技能都可以使用无限次。
请问度度熊最少携带多少晶石，就可以消灭所有的怪兽。
本题包含若干组测试数据。
第一行两个整数n，m,表示有n个怪兽，m种技能。
接下来n行，每行两个整数，a[i],b[i]，分别表示怪兽的生命值和防御力。
再接下来m行，每行两个整数k[i]和p[i]，分别表示技能的消耗晶石数目和技能的伤害值。
数据范围:
1<=n<=100000
1<=m<=1000
1<=a[i]<=1000
0<=b[i]<=10
0<=k[i]<=100000
0<=p[i]<=1000
对于每组测试数据，输出最小的晶石消耗数量，如果不能击败所有的怪兽，输出-1
1 2 3 5 7 10 6 8 1 2 3 5 10 7 8 6
6 18
#include<bits/stdc++.h> using namespace std; typedef __int64 ll; ll dp[2004][12]; ll a[100005],b[100005],k[2004],p[2004]; const ll INF=1e18; int main() { int n,m; while(~scanf("%d%d",&n,&m)) { for(int i=1; i<=n; i++) scanf("%I64d%I64d",&a[i],&b[i]); for(int i=1; i<=m; i++) scanf("%I64d%I64d",&k[i],&p[i]); for(int i=0; i<2004; i++) for(int j=0; j<=10; j++) dp[i][j]=INF; for(int i=0; i<=10; i++) { dp[0][i]=0; for(int j=1; j<=m; j++) if(p[j]>i) { for(int l=p[j]-i; l<2004; l++) dp[l][i]=min(dp[l-p[j]+i][i]+k[j],dp[l][i]); } for(int j=2002; j>=0; j--) dp[j][i]=min(dp[j][i],dp[j+1][i]); } ll ans=0; for(int i=1; i<=n; i++) ans+=dp[a[i]][b[i]]; if(ans>=INF) puts("-1"); else printf("%I64d ",ans); } }
度度熊的午饭时光
度度熊最期待每天的午饭时光，因为早饭菜品清淡，晚饭减肥不敢吃太多（胖纸的忧伤T.T）。
百度食堂的午餐超级丰富，祖国各大菜系应有尽有，度度熊在每个窗口都有爱吃的菜品，而且他还为喜爱的菜品打了分，吃货的情怀呀(>.<)。
但是，好吃的饭菜总是很贵，每天的午饭预算有限，请帮度度熊算一算，怎样打饭才能买到的最好吃的饭菜?(不超过预算、不重样、午餐等分最高的情况下，选择菜品序号加和最小，加和相等时字典序最小的组合)
第一行一个整数T，表示T组数据。 每组测试数据将以如下格式从标准输入读入：
B
N
score_1 cost_1
score_2 cost_2
:
score_N cost_N
第一行，正整数B（0 <= B <= 1000），代表午餐的预算。
第二行，正整数N (0 <= N <= 100)，代表午餐可选的菜品数量
从第三行到第 (N + 2) 行，每行两个正整数，以空格分隔，score_i表示菜品的得分，cost_i表示菜品的价格(0 <= score_i, cost_i <= 100)。
对于每组数据，输出两行： 第一行输出："Case #i:"。i代表第i组测试数据。 第二行输出菜品的总得分和总花费，以空格分隔。 第三行输出所选菜品的序号，菜品序号从1开始，以空格分隔。
2 29 6 9 10 3 4 6 5 7 20 10 9 15 11 0 2 2 23 10 12
Case #1: 34 29 2 3 5 6 Case #2: 0 0
#include<bits/stdc++.h> using namespace std; int c[105],w[105],dp[10005],a[105][10005],f[105],num,cost; int main() { int T,ca=1; scanf("%d",&T); while(T--) { int m,n; scanf("%d%d",&m,&n); for(int i=1; i<=n; i++) scanf("%d%d",&c[i],&w[i]); memset(dp,0,sizeof(dp)); memset(a,0,sizeof(a)); a[0][0]=1; for(int i=1; i<=n; i++) { for(int j=m; j>=w[i]; j--) { if(dp[j]<dp[j-w[i]]+c[i]) { dp[j]=dp[j-w[i]]+c[i]; a[i][j]=1; } } } num=100; cost=0; int ff=m; for(int i=n; i>=1; i--) if(a[i][ff]) { f[num--]=i; ff-=w[i]; cost+=w[i]; } printf("Case #%d: %d %d ",ca++,dp[m],cost); if(num<100) { printf("%d",f[num+1]); for(int i=num+2; i<101; i++) printf(" %d",f[i]); printf(" "); } } return 0; }