程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ1717 Dominoes DP,背包的變形

POJ1717 Dominoes DP,背包的變形

編輯:C++入門知識

POJ1717 Dominoes DP,背包的變形


這道題目比較短,而且有圖片很容易懂題意,就是每一張牌,分為上下兩部分,上面有幾個點,代表上部分為幾,下面同樣,然後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]

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved