這道題目比較短，而且有圖片很容易懂題意，就是每一張牌，分為上下兩部分，上面有幾個點，代表上部分為幾，下面同樣，然後n張牌平行豎直放置，這樣每一張牌的上面部分組成第一行，下面部分組成第二行，上下兩行的和是有差異的值為gap，每一張牌可以上下反一下，這樣可以是的差異值gap縮小，問你使得gap值最小 需要翻牌的最少次數
首先這道題目跟POJ1837有點類似，但是 邊界設置這道題明顯會麻煩許多，因為之前做過了POJ1837，所以這道題一上來就選擇了那個方法，但是a,b值的差異極端為6000，又有負的，為了代表負數 所以數組就得開到12000，這樣n又為1000，就是10的7次方多的這樣就會超時，所以一直在想辦法優化，去推一維的，然後想到了辦法簡直，可以設定一個邊界，然後每次從左邊掃到右邊的范圍 根據a,b的輸入來進行更新，這樣就不用每次都那麼極端的去掃12000了，於是開始敲起來,
因為有a - b可能產生負數，所以就數組開為最大值的兩倍也就是 6000 * 2，然後邊界設定在6000，dp[i][j]代表前i個此時差異值為j的 最少翻轉次數，狀態轉移就是背包的轉移方式
dp[i][j] = min(dp[i][j],dp[i-1][j - (ai - bi)] + 1);
然後就是因為題目所求的值的只是存在的緣故所以可以優化，這個具體的理由這個博客說的很好：戳這裡
但是我一直RE，後來看到這個博主把邊界設定在20000，為什麼是20000呢，我RE肯定是RE在數組的下邊界，因為有個減法的存在可能會導致下標為負數的，一直沒想明白，結果就從下午拖到了晚上，後來發現錯在這裡 ，就是假設gap值為 x ，那麼 某一張牌的 上面值a = 2,下面值b = 1,翻轉以後 gap值會縮小2，也就是x - 2，這樣開6000就不行了，因為極端情況會產生減去12000的情況，最後經過了 20多把的提交終於AC了
而後我又讓一個巨巨去做了一下，他直接用了我一開始想到的那個辦法，也就是我認為會超時的辦法，結果他過了，而且 他第一次交的數組也不夠大，也過了，這道題數據應該是有問題的，同時也給出那個巨巨的代碼
int nnn;
int aa[1000 + 55];
int bb[1000 + 55];
int cc[1000 + 55];
int dp[100000 + 55];
int suma,sumb;
int sumcc;
int le,ri;
void init() {
suma = sumb = sumcc = 0;
memset(aa,0,sizeof(aa));
memset(bb,0,sizeof(bb));
memset(cc,0,sizeof(cc));
memset(dp,0x7f,sizeof(dp));
}
int Abs(int x) {
return x < 0 ? -x : x;
}
bool input() {
while(cin>>nnn) {
for(int i=1;i<=nnn;i++) {
cin>>aa[i]>>bb[i];
suma += aa[i];
sumb += bb[i];
cc[i] = aa[i] - bb[i];
sumcc += cc[i];
}
return false;
}
return true;
}
void cal() {
int ans = dp[0];
le = ri = 12000;
dp[12000] = 0;
for(int i=1;i<=nnn;i++) {
if(cc[i] > 0)
for(int j=ri + cc[i] * 2;j>=le + cc[i] * 2;j--)
dp[j] = min(dp[j],dp[j - cc[i] * 2] + 1);
else if(cc[i] < 0)
for(int j=le + cc[i] * 2;j<=ri + cc[i] * 2;j++)
dp[j] = min(dp[j],dp[j - cc[i] * 2] + 1);
ri = max(ri,ri + cc[i] * 2);
le = min(le,le + cc[i] * 2);
}
for(int i=0;i<=nnn;i++) {
if(12000 + sumcc - i < 0)continue;/******/
if(ans > dp[12000 + sumcc - i] || ans > dp[12000 + sumcc + i]) {
ans = min(dp[12000 + sumcc - i],dp[12000 + sumcc + i]);
cout<
巨巨的代碼：
#include
#include
#include
using namespace std;
const int N = 1000+5;
const int Inf = 1<<30;
int dp[N][N<<4], a[N], b[N];
int n;
inline void Update(int &x, int y) {
if(x > y) x = y;
}
void solve() {
int mid = 6000;
for(int i = 0;i <= n; i++) {
for(int j = 0;j <= mid*2; j++)
dp[i][j] = Inf;
}
dp[0][mid] = 0;
for(int i = 1;i <= n; i++) {
for(int j = 0;j <= mid*2; j++) if(dp[i-1][j] < Inf) {
Update(dp[i][j+a[i]-b[i]], dp[i-1][j]);
Update(dp[i][j-a[i]+b[i]], dp[i-1][j]+1);
}
}
for(int i = 0;i <= mid; i++) if(dp[n][i+mid]
