P7535 [COCI2016-2017#4] Kas 题解

V1mnkE · 2022-07-17 20:44:16 · 题解

校内模拟赛的题

思路

看到这道题可以很快想出一个 O(n (\sum c_i)^2) 的方法：用 dp_{i,j,k} 表示表示第 1 \sim i 张钞票里，能否使得 Kile 分到 j 块钱，Pogi 分到 k 块钱，可以得到状态转移方程：

但是这样空间要开到 500\times 500\times 10^5 ，会爆空间。所以我们再观察一下，可以用一个显然的结论来优化空间：知道两个数的和、差就可以求出这两个数的值。我们重新定义一下 dp 数组，令 dp_{i,j} 表示第 1 \sim i 张钞票里， Kile 和 Pogi 分到钱的差值为 j 时，两人钱数之和的最大值， 可以得到柿子：

注意到每次转移第一维只从 i-1 转移过来，可以用滚动数组优化，不过不加也可以过。

代码

#include<bits/stdc++.h>
using namespace std;
int n,a[600],dp[505][100005],tot,now;
int main(){
    memset(dp,-0x7f,sizeof(dp));
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        tot+=a[i];
    }
    dp[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=tot;j++){
            dp[i][j]=max(dp[i-1][j],max(dp[i-1][j+a[i]]+a[i],dp[i-1][abs(j-a[i])]+a[i]));
        }
    }   
    cout<<tot-dp[n][0]/2;
    return 0;
}