题目链接：http://codeforces.com/contest/730/problem/J
题目大意：
有n个瓶子。每个瓶子有饮料a[i]。瓶子的体积为b[i]。现在想把所有的饮料倒在k个瓶子里。而且每倒一升的饮料。需要花费时间1。现在希望k最小的情况下并且花费的总时间t最少。
思路：我们可以直接求k。因为要优先满足k。那么就是： sort(b+1,b+n+1):i=1∑kb[i]>=i=1∑na[i]
直接计算就可以了。
因为我们要把所有的饮料倒在这k个瓶子里面。那么这k个瓶子里面剩余的饮料越多越好。直接dp：
dp[i][j][k]:前i个瓶子中选择j个瓶子，使得这j个瓶子的容量为k，这k个瓶子的最多剩余饮料
转移方程:
f(n)={dp[i][j][k]=max(d[i−1][j][k],dp[i−1][k−1][k−b[i]]+a[i]),dp[i][j][k]=d[i−1][j][k],j>=b[i]j<b[i]
显然要降维：
#include <bits/stdc++.h>
using namespace std;
int a[105], b[105], c[105], f[105][10005];
int main()
{
int n, m;scanf("%d", &n);
int sum=0, k=0;
for(int i=1; i<=n; i++){
scanf("%d", &a[i]);
sum+=a[i];
}
m=sum;//a[]的和
for(int i=1; i<=n; i++){
scanf("%d", &b[i]);
c[i]=b[i];
}
sort(c+1, c+1+n);
for(int i=n; i>=1; i--){//求k
sum-=c[i];
k++;
if(sum<=0){
break;
}
}
memset(f, -1, sizeof(f));
f[0][0]=0;
for(int i=1; i<=n; i++){
for(int j=i; j>=1; j--){
for(int k=10000; k>=b[i]; k--){
if(f[j-1][k-b[i]]!=-1){
f[j][k]=max(f[j][k], f[j-1][k-b[i]]+a[i]);
//cout<<i<<" "<<j<<" "<<k<<" "<<f[j][k]<<endl;
}
}
}
}
int mx=0;
for(int i=m; i<=10000; i++){
mx=max(mx, f[k][i]);
}
printf("%d %d\n", k, m-mx);
return 0;
}
京公网安备 11010502036488号