題面描述 試題描述 小a和小b玩一個游戲，有n張卡牌，每張上面有兩個正整數x,y。 取一張牌時，個人積分增加x，團隊積分增加y。 求小a，小b各取若幹張牌，使得他們的個人積分相等。 輸入 第一行一個整數n。接下來n行，每行兩個整數x,y，用空格隔開。 輸出 一行一個整數，表示小a的積分和小b的積分相 ...
題面描述
試題描述
小a和小b玩一個游戲，有n張卡牌，每張上面有兩個正整數x,y。
取一張牌時，個人積分增加x，團隊積分增加y。
求小a，小b各取若幹張牌，使得他們的個人積分相等。
輸入
第一行一個整數n。
接下來n行，每行兩個整數x,y，用空格隔開。
輸出
一行一個整數，
表示小a的積分和小b的積分相等的時候，團隊積分的最大值。
輸入示例
4
3 1
2 2
1 4
1 4
輸出示例
10
其他說明
對於100%的數據，0<n<=100，1<x<=1e3，0<y<=1e6。
與這個題相比其實poj上有一個與本題類似但是更加經典的例題 題目傳送門
本題乍一看很像一道經典的“取與不取”的01背包問題（x當作重量 y當作價值）但是仍然存在很多問題需要註意
1、如何解決二人同時取的問題？
首先我們來分析一下 由於數據較大避免MLE 所以最多二維dp
但是本題中同時存在三個變數：二人的取法 以及此時取到第幾張
由於最後要求二人數目一樣
也就是要求二人數目差為0（劃重點！！！）
所以我們將二人的取法根據二人數目差壓縮為一個變數
由此可得：dp[i][j]表示取到第i張牌二人差為j時團隊積分的最大值（1<=i<=n -50000<=j<=50000)
dp[0][0]=0
2、如何解決y為負數的情況？
這裡我們要用到一個技巧：狀態偏移
所以我們可以用k+60000表示當j=k+10000的情況（多加一點避免出現其他狀況）
由此可得：dp[i][j]表示取到第i張牌二人差為j-60000時團隊積分的最大值（1<=i<=n 60000<=j<=120000)
dp[0][60000]=0
3、狀態如何進行轉移？
對於本題來講 對於第i張牌存在3種狀態：a取、b取、不取
但是這裡要註意一點 並不是所有的dp[i][j]都是有效狀態（不是所有到第i張牌的取法都能夠找出差為j的方法）
如何處理這種狀態？
首先我們將dp數組整體置為-1
由於不存在的狀態一定不可能被其他方法取到（即dp[i][j]=-1)
而正常的dp[i][j]可以由max(dp[i-w[k][j]+c[k],dp[i][j-w[k]+c[k]）轉移到
於是我們可以將兩種狀態統一起來
首先我們先將dp[i][j]由max(dp[i-w[k][j],dp[i][j-w[k])轉移
不難推出如果dp[i][j]不為無效狀態則dp[i][j]！=-1
如果dp[i][j]！=-1則dp[i][j]+=c[k]
同樣的
dp[i][j]在保證第i張牌不取時可以由dp[i-1][j]轉移
為了確保我們取到了最大的情況 可以對dp[i][j]和dp[i-1][j]的大小進行比較
如果dp[i-1][j]>dp[i][j] 就讓dp[i][j]返回不取的情況（dp[i][j]=dp[i-1][j])
綜上所述，我們得到的轉移方程：
dp[i][j]=max(dp[i-1][j-x[i]],dp[i-1][j+x[i]])
if(dp[i][j]!=-1)dp[i][j]+=y[i]
if(dp[i][j]<dp[i-1][j])dp[i][j]=dp[i-1][j]
好了上代碼吧
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int dp[150][200050],x[150],y[150],n; int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]); memset(dp,-1,sizeof(dp)); dp[0][100000]=0; for(int i=1;i<=n;i++) { for(int j=20000;j<=200005;j++) { dp[i][j]=max(dp[i-1][j-x[i]],dp[i-1][j+x[i]]); if(dp[i][j]!=-1)dp[i][j]+=y[i]; if(dp[i][j]<dp[i-1][j])dp[i][j]=dp[i-1][j]; } } printf("%d",dp[n][100000]); return 0; }
本題是一道較為複雜的01背包問題，有必要將本題的想法、轉移方程及表示徹底學會。
