度度熊与邪恶大魔王
度度熊为了拯救可爱的公主，于是与邪恶大魔王战斗起来。
邪恶大魔王的麾下有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[][];
ll a[],b[],k[],p[];
const ll INF=1e18;
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
for(int i=; i<=n; i++)
scanf("%I64d%I64d",&a[i],&b[i]);
for(int i=; i<=m; i++)
scanf("%I64d%I64d",&k[i],&p[i]);
for(int i=; i<; i++)
for(int j=; j<=; j++)
dp[i][j]=INF;
for(int i=; i<=; i++)
{
dp[][i]=;
for(int j=; j<=m; j++)
if(p[j]>i)
{
for(int l=p[j]-i; l<; l++)
dp[l][i]=min(dp[l-p[j]+i][i]+k[j],dp[l][i]);
}
for(int j=; j>=; j--)
dp[j][i]=min(dp[j][i],dp[j+][i]);
}
ll ans=;
for(int i=; i<=n; i++)
ans+=dp[a[i]][b[i]];
if(ans>=INF)
puts("-1");
else printf("%I64d\n",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[],w[],dp[],a[][],f[],num,cost;
int main()
{
int T,ca=;
scanf("%d",&T);
while(T--)
{
int m,n;
scanf("%d%d",&m,&n);
for(int i=; i<=n; i++)
scanf("%d%d",&c[i],&w[i]);
memset(dp,,sizeof(dp));
memset(a,,sizeof(a));
a[][]=;
for(int i=; 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]=;
}
}
}
num=;
cost=;
int ff=m;
for(int i=n; i>=; i--)
if(a[i][ff])
{
f[num--]=i;
ff-=w[i];
cost+=w[i];
}
printf("Case #%d:\n%d %d\n",ca++,dp[m],cost);
if(num<)
{
printf("%d",f[num+]);
for(int i=num+; i<; i++)
printf(" %d",f[i]);
printf("\n");
} }
return ;
}