zoj3816(dfs + 數位DP)

zoj3816(dfs + 數位DP)

題意:

給出一個數n,從比n小的數中選出一個最大的;

滿足壓縮完是回文數,壓縮指連續的相同數字,只算一個;

如1221就算做121;

1121算作121;

思路:

我們就是要從左邊開始構造一個數;

首先我們在第一位放了一個數字;那麼我們就要在最後一位放一個數字,為了讓他們對稱;

但是有幾種情況,只需在左邊放一個,而不需要在右邊放;

就是出現重復數字的時候還有只剩一個位置的時候;

如果我們在最左邊放了一個1,那麼就要在最右邊也放一個,然後我們再放一個1,就不需要在右邊放了,因為左邊兩個1只算作1個;

然後我們在左邊放完一個數字後,可以選擇在右邊放一個這個數字,也可以放兩個;

知道左邊放的數字個數,和右邊放的數字個數和等於總長度為止,然後算出這個數字是不是超出了;

其中我們還用到了數位dp中的s狀態位,來判斷這一位能放的最大值是多少;

#include
#include
#include
using namespace std;
#define ll long long

ll n;
char str[20];
ll left[20];
ll right[20];
ll len;
ll dfs(int l, int r, int s) {
	ll ans = -1;
	if(l + r >= len) {
		if(l + r > len)
			return -1;
		ans = 0;
		for(int i = 0; i < l; i++) {
			ans = ans * 10 + left[i];
		}
		for(int i = r; i >= 1; i--) {
			ans = ans * 10 + right[i];
		}
		if(ans >= n)
			ans = -1;
		return ans;
	}
	int m = s ? (str[l] - '0') : 9;
	for(int i = m; i >= 0; i--) {
		left[l] = i;
		if(l != 0 && left[l] == left[l - 1]||l == 0 && i == 0 || l + r == len - 1) {
			ans = max(ans, dfs(l + 1, r ,s && (str[l] - '0'== i)));
		}
		else {
			for(int j = r + 1; l + j <= len - 1; j++) {
				right[j] = i;
				ans = max(ans, dfs(l + 1, j, s && (str[l] - '0'== i)));
			}
		}
		if(ans > 0)
			return ans;
	}
	return ans;
}
int main() {
	int t;
	scanf("%d",&t);
	while(t--) {
		scanf("%s",str);
		len = strlen(str);
		sscanf(str,"%lld", &n);
		printf("%lld\n",dfs(0,0,1));
	}
}