傳送門

?

f[i][j]表示前i個數余數為j的最優解

sum[i][j]表示字符串i~j所構成的數

?

#include <cstdio> #include <cstring> #define N 1001 #define min(x, y) ((x) < (y) ? (x) : (y))int n, p; char s[N]; int f[N][51], sum[N][N];int main() {int i, j, k;scanf("%s", s + 1);n = strlen(s + 1);scanf("%d", &p);for(i = 1; i <= n; i++)for(j = i; j <= n; j++)sum[i][j] = (sum[i][j - 1] * 10 + s[j] - '0') % p;memset(f, 127 / 3, sizeof(f));for(i = 1; i <= n; i++) f[i][sum[1][i]] = 0;for(i = 1; i <= n; i++)for(j = 0; j < p; j++)for(k = 1; k < i; k++)f[i][j * sum[k + 1][i] % p] = min(f[i][j * sum[k + 1][i] % p], f[k][j] + 1);for(i = 0; i < p; i++)if(f[n][i] < 707406378){printf("%d %d ", i, f[n][i]);break;}for(i = p - 1; i >= 0; i--)if(f[n][i] < 707406378){printf("%d %d ", i, f[n][i]);break;}return 0; }

　　

轉載于:https://www.cnblogs.com/zhenghaotian/p/7337981.html

總結

以上是生活随笔為你收集整理的[luoguP1773] 符文之语_NOI导刊2010提高（02）（DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。