程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU2089 不要62 數位DP

HDU2089 不要62 數位DP

編輯：C++入門知識

數位DP第一道題目，昨晚是做了4個小時，參考了一下方程，最後搞出來了，但是很亂，先給上昨天的代碼

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define ll long long

#define eps 1e-8

#define inf 0xfffffff

//const ll INF = 1ll<<61;

using namespace std;

//vector > G;
//typedef pair P;
//vector > ::iterator iter;
//
//mapmp;
//map::iterator p;

int n,m;

int dp[10][3];//dp[i][j],前i位數的狀態，

/*
dp[i][0],表示前i位數且不含不吉利數的個數
dp[i][1],表示前i位數開頭放了2的數的個數
dp[i][2],表示前i位數含不吉利數的個數
*/

int num[12];

void init() {
	memset(dp,0,sizeof(dp));
	dp[0][0] = 1;
	for(int i=1;i<=6;i++) {
		dp[i][0] = dp[i-1][0] * 9 - dp[i-1][1];//構造一下前i位不含不吉利數個數，因為最後以為可能取6，與下一步的開頭取2湊成了不吉利數，所以減去
		
		dp[i][1] = dp[i-1][0];//開頭為2的前i位數 就是不含不吉利數前i-1數

		dp[i][2] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] * 10;//含有的話一個是本身就含有，那麼到了i位就是i-1位乘10，還有前i-1位數不含有因為多了一個4而產生了，最後就是開頭為2，因為6而產生了
	}
}

void clear() {
	memset(num,0,sizeof(num));
}

int cal(int x) {
	clear();
	int cnt = 1;
	int tmpx = x;
	while(tmpx) {
		num[cnt++] = tmpx%10;
		tmpx /= 10;
	}
	num[cnt] = 0;
	bool flag = false;
	int ans = 0;
	for(int i=cnt;i>=1;i--) {
		ans += dp[i-1][2] * num[i];
		if(flag)//已經為不吉利
			ans += dp[i-1][0] * num[i];
		if(!flag && num[i] > 4)//此位大於4，後面可有4
			ans += dp[i-1][0];
		if(!flag && num[i+1] == 6 && num[i] > 2)//後一位是6，此位大於2
			ans += dp[i][1];
		if(!flag && num[i] > 6)//此位大於6
			ans += dp[i-1][1];
		if((num[i] == 2 && num[i+1] == 6) || num[i] == 4) //導致不吉利
			flag = true;
	}
	return x - ans;
}

int main() {
	init();
	while(scanf("%d %d",&n,&m), n + m) {
		clear();
		int ans = cal(m+1) - cal(n);
		printf("%d\n",ans);
	}
	return EXIT_SUCCESS;
}

今天想回頭再去看看，最後發現百度裡有一個數位DP的文檔還是很不錯的

http://wenku.baidu.com/link?url=o3ER_gVCyB0qcKthM-Y8vPtAGZ_u5bzOu_gUCUhPcXC6YfaSDgtBSXNEEvvGvSzyuDE9TULcPNsDrRd9IUtQVHeKUVrnPUjyfWjCly_J7Xq

這個文檔非常好，而且裡面有這道題目的剖析，做法跟我昨天的不一樣，但是更好理解，所以按照他的剖析自己寫了一下，做出來了，還是比較開心的，忍不住多贊一下這個文檔，給出新思路的代碼

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define ll long long

#define eps 1e-8

#define inf 0xfffffff

//const ll INF = 1ll<<61;

using namespace std;

//vector > G;
//typedef pair P;
//vector > ::iterator iter;
//
//mapmp;
//map::iterator p;


int dp[12][12];//開頭為j的i位數
int num[10];

void clear() {
	memset(dp,0,sizeof(dp));
	dp[0][0] = 1;
	for(int i=1;i<=6;i++) {
		for(int j=0;j<10;j++) {
			for(int k=0;k<10;k++) {
				if(j != 4 && (j != 6 || k != 2))
					dp[i][j] += dp[i-1][k];
			}
		}
	}
}

int cal(int x) {
	memset(num,0,sizeof(num));
	int cnt = 1;
	int tmpx = x;
	while(tmpx) {
		num[cnt++] = tmpx%10;
		tmpx /= 10;
	}
	int ans = 0;
	for(int i=cnt;i>=0;i--) {
		for(int j=0;j