Luogu P1874 快速求和 DP

传送门
dp[i][j]表示前前i位组成数字k的最小次数，预处理出s[i][j]表示数位i到j表示的数字
状态转移方程即为：dp[i][k] = min(dp[i][k], dp[j - 1, k - s[i][j]] + 1).
dp[0][0] = 0, 其余为大数字
当遇到s[i][j]大于n时，将s[i][j]设为一个大数，以免爆int

#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 1000000
using namespace std; 

int num[100], len, n;
int dp[50][100001], s[100][100]; //前i位组成数字k的最小次数
//dp[i][k] =  min(dp[i][k], dp[i - 

void read(){
	char ch = getchar();
	while(ch < '0' || ch > '9') ch = getchar();
	while(ch >= '0' && ch <= '9') num[++len] = ch - '0', ch = getchar();
	return;
}

int main(){
	for(int i = 0; i < 50; i++){
		for(int j = 0; j < 100001; j++){
			dp[i][j] = 1000000;
		}
	}
	for(int i = 0; i < 100; i++){
		for(int j = 0; j < 100; j++){
			s[i][j] = 1000000;
		}
	}
	read();
	scanf("%d", &n);
	
	//[i, i+l]数字，若大于100000设为INF 
	for(int i = 1; i <= len; i++){
		s[i][i] = num[i];
	}
	for(int l = 1; l <= len; l++){
		for(int i = 1; i + l <= len; i++){
			int tmp = s[i][i+l-1]*10 + num[i + l];
			if(tmp > 100000ll) s[i][i+l] = INF;
			else s[i][i+l] = tmp;
		}
	}
	
//	for(int i = 1; i <= len; i++){
//		for(int j = i; j <= len; j++){
//			printf("s[%d][%d] = %d
", i, j, s[i][j]);
//		}
//	}
	
	dp[0][0] = 0;
	
	for(int i = 1; i <= len; i++){
		for(int j = 1; j <= i; j++){
//			printf("%d %d
", i, j);
			int val = s[j][i];
//			printf("val = %d
", val);
			if(s[j][i] > 100000) continue;
			for(int k = val; k <= n; k++){
//				printf("k = %d
", k);
//				printf("%d %d    %d %d
", j - 1, k - val, i, k);
				if(dp[j - 1][k - val] + 1 < dp[i][k]){
					dp[i][k] = dp[j - 1][k - val] + 1;
//					printf("dp[%d][%d] = %d
", i, k, dp[i][k]);
				}
//				dp[i][k] = min(dp[i][k], dp[j - 1][k - val] + 1);
			}
//			int l = i - j + 1;
		}
	}
	if(dp[len][n] > 100) dp[len][n] = 0;
	printf("%d", dp[len][n] - 1);
	return 0;
}