CodeForces - 1463E Glass Half Spilled(dp)

題目鏈接：點擊查看

題目大意：給出 n 個水杯，每個水杯最大容量為 a i a_i ai?，每個水杯初始時有 b i b_i bi? 的水，兩個水杯之間可以互相倒水，不過每次會損失一半水量，更具體的說，假設第 i i i 個水杯向第 j j j 個水杯中倒 x x x 單位的水（ x x x可以為任意實數），那么操作之后兩個杯子中的水會變為： b i ? x ， b j + x 2 b_i-x，b_j+\frac{x}{2} bi??x，bj?+2x?，現在可以執行任意次數的倒水操作，

假設最終需要選則 k k k 個杯子，使得其水量之和盡量大，問最大可以是多少

現在問選取 k ∈ [ 1 , n ] k \in [ 1,n] k∈[1,n] 時的答案

題目分析：比賽的時候想到是 d p dp dp 了，但是推出了一個帶有后效性的轉移，然后自己把自己給否定了，沒有繼續思考下去，有點可惜

先不考慮倒水操作，那么設 d p i , j , k dp_{i,j,k} dpi,j,k?為前 i i i 個杯子中，選擇了 j j j 個杯子，杯子容量上限之和 ( ∑ a ) (\sum a) (∑a)為 k k k 時的最大水量之和 ( ∑ b ) (\sum b) (∑b)，不難看出這是一個背包的變形，直接列舉轉移即可，同時可以將第一維滾動進行，轉移方程如下：
d p i , j , k = m a x { d p i ? 1 , j , k 不 選 擇 第 i 項 d p i ? 1 , j ? 1 , k ? a i + b i 選 擇 第 i 項 dp_{i,j,k}=max \left\{ \begin{aligned} &dp_{i-1,j,k} &不選擇第i項\\ &dp_{i-1,j-1,k-a_i}+b_i&選擇第i項\\ \end{aligned} \right. dpi,j,k?=max{?dpi?1,j,k?dpi?1,j?1,k?ai??+bi??不選擇第i項選擇第i項?

最后直接列舉狀態維護最大值即可，假設初始時所有水量之和為 s u m b sumb sumb 現在需要選擇 j j j 個杯子，且最大容量為 k k k 時，此時的答案就是 m i n ( d p i , j , k + s u m b ? d p i , j , k 2 , k ) min(dp_{i,j,k}+\frac{sumb-dp_{i,j,k}}{2},k) min(dpi,j,k?+2sumb?dpi,j,k??,k)了，化簡一下，且內部同時乘以 2 2 2，則變成了 m i n ( d p i , j , k + s u m b , 2 ? k ) min(dp_{i,j,k}+sumb,2*k) min(dpi,j,k?+sumb,2?k)，維護一下最大值就可以了

代碼：

// #pragma GCC optimize(2)
// #pragma GCC optimize("Ofast","inline","-ffast-math")
// #pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<unordered_map>
using namespace std;
 
typedef long long LL;
 
typedef unsigned long long ull;
 
const int inf=0x3f3f3f3f;
 
const int N=110;
 
int a[N],b[N],dp[2][N][N*N];
 
int main()
{
#ifndef ONLINE_JUDGE
 // freopen("data.in.txt","r",stdin);
 // freopen("data.out.txt","w",stdout);
#endif
//  ios::sync_with_stdio(false);
	int n,sa=0,sb=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",a+i,b+i);
		sa+=a[i];
		sb+=b[i];
	}
	for(int j=0;j<=n;j++)
		for(int k=0;k<=sa;k++)
			dp[0][j][k]=-inf;
	dp[0][0][0]=0;
	int t=1;
	for(int i=1;i<=n;i++,t^=1)
	{
		for(int j=0;j<=n;j++)//不選第i個杯子
			for(int k=0;k<=sa;k++)
				dp[t][j][k]=dp[t^1][j][k];
		for(int j=1;j<=n;j++)//選第i個杯子
			for(int k=a[i];k<=sa;k++)
				dp[t][j][k]=max(dp[t][j][k],dp[t^1][j-1][k-a[i]]+b[i]);
	}
	for(int i=1;i<=n;i++)
	{
		int ans=0;
		for(int j=0;j<=sa;j++)
			ans=max(ans,min(2*j,dp[t^1][i][j]+sb));
		printf("%.10f ",ans/2.0);
	}
	puts("");
    return 0;
}