AT_dp_m Candies这是一道比较典型的前缀和优化dp设dp[i][j]表示前i个人分j个糖果方案那么我们枚举第i个人分到的糖果k然后累加前i-1个人分到j-k糖果的方案所以dp方程为:这样的复杂度是显然无法通过发现dp[i]只由dp[i-1]转移那么我们每次转移前先用一个数组记录出dp[i-1]设然后每次可以O(1)转移时间复杂度优化到了O(nm)代码如下#includebits/stdc.h using namespace std; #define int long long #define _for(i,a,b) for(int i (a) ; i (b) ; i ) #define for_(i,a,b) for(int i (a) ; i (b) ; i --) int n,m; const int maxm 110; const int mod 1e9 7; const int maxn 1e5 10; int sum[maxn]; int a[maxm]; int dp[maxm][maxn]; signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin n m; _for(i , 1 , n) cin a[i]; _for(i , 1 , n) { dp[i][0] 1; sum[0] 1; } _for(i , 1 , n){ _for(j , 1 , m) sum[j] (sum[j - 1] dp[i - 1][j]) % mod; _for(j , 1 , m) { if(j - a[i] - 1 0) dp[i][j] (sum[j] - sum[j - a[i] - 1] mod) % mod; else dp[i][j] sum[j] % mod; } } cout dp[n][m] % mod; return 0; }AT_dp_o Matching没切出来看到n显然想到状压由于是男女匹对所以我们dp状态里需要同时限制男生和女生由于n是20左右显然不能把男女生的匹配方案全部状压那么考虑状压女生被匹配的方案另一位存男生被匹配的数量但是事实上这两个约束可以合并成一个由于男女一一配对所以男生被匹配的数量和女生被匹配的数量相等所以我们只需要数女生被匹配的状态ss中的1的数量即为男生女生被匹配的人数所以我们设dp[s]表示女生被匹配的状态s的方案总数那么考虑目前的第i个男生遍历i男生可以匹配的女生p如果未被匹配的话将(i,p)配对那么此时的方案是j集合中删去p的方案数对所有情况求和即可#includebits/stdc.h using namespace std; #define int long long #define _for(i,a,b) for(int i (a) ; i (b) ; i ) #define for_(i,a,b) for(int i (a) ; i (b) ; i --) const int maxn 22; int dp[1 maxn]; int n,ans; int a[maxn][maxn]; const int mod 1e9 7; signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin n; _for(i , 1 , n) { _for(j , 1 , n) cin a[i][j]; } dp[0] 1; _for(i , 0 , (1 n) - 1){ _for(j , 1 , n){ if((i (j - 1)) 1) { int k __builtin_popcount(i); if(a[k][j]) { dp[i] dp[i - (1 (j - 1))]; dp[i] % mod; } } } } cout dp[(1 n) - 1] % mod; return 0; }AT_dp_p Independent Set很典型的树形dp设dp[u][0/1]表示以u为根子树u是白/黑子树总染色方案那么考虑总方案是乘法原理即每个子树的方案之积但是注意若u是黑色子树不能是黑色所以得到转移方程初始化每一个dp[u][0] dp[u][1]1代码如下#includebits/stdc.h using namespace std; #define int long long #define _for(i,a,b) for(int i (a) ; i (b) ; i ) #define for_(i,a,b) for(int i (a) ; i (b) ; i --) const int maxn 1e5 10; int dp[maxn][2]; vectorintv[maxn]; const int mod 1e9 7; int n; void dfs(int u,int fa){ dp[u][0] 1; dp[u][1] 1; for(auto itr:v[u]){ if(itr fa) continue; dfs(itr,u); dp[u][0] * (dp[itr][0] dp[itr][1]) % mod; dp[u][0] % mod; dp[u][1] * dp[itr][0]; dp[u][1] % mod; } } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin n; _for(i , 1 , n - 1){ int x,y; cin x y; v[x].push_back(y); v[y].push_back(x); } dfs(1,0); cout (dp[1][0] dp[1][1]) % mod; return 0; }