第一次遇到需要先枚舉然後再數位DP的。 先枚舉各位數之和,即,1~81,然後數位DP過程中再判斷枚舉的各位數之和與枚舉的數是否相同,只有相同的才算。 dp[i][j][k][h]表示第i位上,當前的各位數和為j,枚舉的各位數和為k,當前的數對k取模為h的數的個數。 代碼如下:
#include #include #include #include #include #include #include #include #include using namespace std; #define LL __int64 #define pi acos(-1.0) const int mod=1e9+7; const int INF=0x3f3f3f3f; const double eqs=1e-9; const int MAXN=200000+10; int dp[11][82][82][82], dig[11]; int dfs(int cnt, int sum, int mods, int res, int maxd) { if(cnt==-1) return sum==mods&&res==0; if(sum>mods) return 0; if(maxd&&dp[cnt][sum][mods][res]!=-1) return dp[cnt][sum][mods][res]; int i, r=maxd?9:dig[cnt], ans=0; for(i=0;i<=r;i++){ ans+=dfs(cnt-1,sum+i,mods,(res*10+i)%mods,maxd||i
class Solution {public: int my
poj1113-Wall Wall
一、寫時拷貝的引入 class String{ f
很有意思的貪心: Let's
第3章 字符串,向量和數組 1. 如何用strin
【題目】 Merge k sorted linked li