CodeForces - 1459D（dp）
90nwyn
2020-12-19 23:31:20
[题目链接](https://vjudge.net/problem/CodeForces-1459D)
------------
$dp[i][j][k]$为在前$i$个杯子中，选了$j$个杯子，其总容量为$k$时，水量总和的最大值（不考虑进行任何操作）
------------
```cpp
#include <bits/stdc++.h>
typedef double db;
using namespace std;
const int M=105;
int n,a[M],b[M],dp[M][M*M],tot,sum;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a[i],&b[i]);
tot+=a[i];sum+=b[i];
}
for(int i=0;i<=n;i++)for(int j=0;j<=tot;j++)dp[i][j]=-0x3f3f3f3f;
dp[0][0]=0;
for(int i=1;i<=n;i++)
for(int j=i;j>=1;j--)
for(int k=tot;k>=a[i];k--)
dp[j][k]=max(dp[j][k],dp[j-1][k-a[i]]+b[i]);
for(int i=1;i<=n;i++)
{
db res=0;
for(int j=1;j<=tot;j++)
res=max(res,min((db)j,(db)dp[i][j]/2+(db)sum/2));
printf("%.9lf ",res);
}
return 0;
}
```