题目链接：http://codeforces.com/problemset/problem/730/J
题目大意：有n个杯子， 每个杯子有两个值一个是已装水量，一个是可装水量。从一个杯子向另一个杯子倒1单位体积的水，时间花费为1s。 现在用n个杯子中的s个来装所有水， 求最小的s， 以及最少花费的时间。
解题思路：有了n杯水的总水量， 可以按照n个杯子的大小排序， 然后就可以求出最小的s。然后就可以将题目看做是求从n个杯子里面选s个，这s个杯子的总的可装水量是大于等于总水量，这种情况下这n个杯子实际装水量的最大值。因为，这s个杯子是可以装下所有水的， 那么花费时间不就其他n-s个杯子里面的总水量， 那么这n-s个杯子的总水量越小那么花费时间越少， 那么就是这s个杯子水量越大。
定义：dp[i][j][k]代表第i个杯子，可装水量为j时， 已选k个杯子的最大实际装水量。
那么递推方程应为dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][i-a[x]][k-1] + b[x]),然后可以优化成二维的，即可求解：
代码如下：
#include<bits/stdc++.h>
using namespace std; pair<int, int> par[];
int dp[][]; bool cmp(const int &a, const int &b)
{
return a > b;
} pair<int, int> cou(int n)
{
int res[], f = ;
for(int i=; i<=n; ++ i)
f += par[i].first, res[i] = par[i].second;
sort(res + , res + n + , cmp);
int s = ;
for(int i=; i<=n; ++ i)
{
s += res[i];
if(s >= f)
return make_pair(s, i);
}
} int main()
{
int n;
scanf("%d", &n); int s = ;
for(int i=; i<=n; ++ i)
{
scanf("%d", &par[i].first);
s += par[i].first;
}
for(int i=; i<=n; ++ i)
scanf("%d", &par[i].second); pair<int, int> t = cou(n);
for(int i=; i<=t.first; ++ i)
{
for(int k=; k<= t.second; ++ k)
{
dp[i][k] = -;
}
}
dp[][] = ;
for(int i=; i<=n; ++ i)
{
for(int j=t.first; j>=par[i].second; -- j)
{
for(int k=; k<=t.second; ++ k)
{
dp[j][k] = max(dp[j][k], dp[j-par[i].second][k-] + par[i].first);
}
}
}
int mx = ;
for(int i=s; i<=t.first; ++ i)
{
if(dp[i][t.second] > mx)
mx = dp[i][t.second];
}
printf("%d %d\n", t.second, s - mx);
}