程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> URAL 2052 Physical Education(數位dp)

URAL 2052 Physical Education(數位dp)

編輯：C++入門知識

URAL 2052 Physical Education(數位dp)

題意：給出一個自然數數列，按照每個數的所有數位之和作為第一關鍵字，每個數的大小作為第二關鍵字升序排序，位置不變的數的個數是多少。

思路：首先可以證明，對於數位和為i的所有數，最多只可能有一個位置不變，這個可以直觀的猜想一下，因為如果有一個數字位置不變，那麼對於排序後的序列，這個數後面的所有數的增長速度都大於自然數序列的增長速度，所以不可能再有第二個。

假設我們當前求出了數位和為i的區間為[l, r]，令query(a, b)表示1到a這段區間內數位和為b的數的個數，用su[i-1]表示數位和為1到i-1的數的個數。

那麼對於區間[l, l+query(l-1, i) -1]，一定不存在位置不變的數，因為這些數都小於l，

那麼我們就把區間縮小為了[su[i-1]+query(l-1, i)+1, su[i-1]+query(r, i)],因為至多只存在一個位置不變的數，所以這個區間肯定可以一直縮小下去，這個遞歸來做就可以。

遞歸的出口是l==r且su[i-1]+query(l-1, i)+1==su[i-1]+query(r,i)，這時返回1，否則返回0。也就是說，這時l位置的這個數就是位置不變的一個數。

現在問題轉化為了求query，對於這個問題，我們用一個輔助的數組dp[][][]幫助我們計算,dp[i][j][k]表示一個第i位為j數字和為k的數有多少,並且第i位是這個數的最高位。

對於query，每次如果當前位的數字比給定的n的這一位的數字小，那麼後面可以隨便選，這樣一來就可以解決query的問題，具體見代碼。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps 1e-6
#define LL long long
using namespace std;

//const int maxn = 100 + 5;
//const int INF = 0x3f3f3f3f;
int n, dp[20][20][100], su[100];
void init() {
	for(int i = 0; i <= 9; i++) dp[1][i][i] = 1;
	for(int i = 2; i <= 10; i++) {
		for(int j = 0; j <= 9; j++) {
			for(int t = 0; t <= 81; t++) {
				for(int k = 0; k <= 9; k++)
					if(t>=j) dp[i][j][t] += dp[i-1][k][t-j];
			}
		}
	}
}
int query(int r, int digit_sum) {
	int digit[20], len=0;
	int tmp = r;
	while(tmp) {
		digit[++len] = tmp % 10;
		tmp /= 10;
	}
	int cur_sum = 0;
	int ans = 0;
	for(int i = len; i >= 1; i--) {
		for(int j = 0; j < digit[i]; j++) {
			if(digit_sum-j-cur_sum >= 0) 
				ans += dp[i][j][digit_sum-cur_sum];
		}
		cur_sum += digit[i];
	}
	if(cur_sum == digit_sum) ans++;
	return ans;	
}
void init_su() {
	for(int i = 1; i <= 81; i++) 
		su[i] = su[i-1] + query(n, i);
}
int solve(int l, int r, int digit_sum) {
	int left_border = su[digit_sum-1] + query(l-1, digit_sum)+1;
	int right_border = su[digit_sum-1] + query(r, digit_sum);
	if(left_border > right_border) return 0;
	if(left_border==right_border) {
		if(su[digit_sum-1]+query(left_border-1,digit_sum)+1 == su[digit_sum-1] + query(right_border, digit_sum)) return 1;
		return 0;
	}
	return solve(left_border, right_border, digit_sum);
}
int main() {
	//freopen(input.txt, r, stdin);
	init();
	while(cin >> n) {
		init_su();
		//for(int i = 1; i <= 9; i++) cout << i << :  << query(n, i) << endl;
		int ans = 0;
		for(int i = 1; i <= 81; i++) ans += solve(su[i-1]+1, su[i], i);
		//for(int i = 1; i <= 10; i++) cout << i << :  << solve(su[i-1]+1, su[i], i) << endl;
		cout << ans << endl;
	}
	return 0;
}