题目大意：n个身高从1-n的人，按照前面比后面矮，右边比左边矮排队，从f[0][0][0][0][0]到f[n1][n2][n3][n4][n5]有多少种方案
题解：对于每个新加进来的人考虑
1.该行未满
2.行号为1，或者该行的学生数比上一行少（这样的话，就能保证如果新插入学生，那么这个学生的高度也比上一行同一位置的学生高度低）
ps：网上说的爆内存问题，其实不需要开到每维31，每维只需要开到30/维数向上取整就可以了，发现没有爆内存
代??
#include <cstdio> #include <cstring> using namespace std; #define ll long long int k ; int n[10] ; ll f[31][16][11][8][7] ; int main(int argc, char const *argv[]) { while(scanf("%d",&k) != EOF) { if(k == 0) break ; memset(f,0,sizeof f) ; memset(n,0,sizeof n) ; for(int i = 1 ; i <= k ; ++ i) scanf("%d",&n[i]) ; while(k < 5) n[++k] = 0 ; f[0][0][0][0][0] = 1 ; for(int i = 0 ; i <= n[1] ; ++ i) { for(int j = 0 ; j <= n[2] ; ++ j) { for(int k = 0 ; k <= n[3] ; ++ k) { for(int l = 0 ; l <= n[4] ; ++ l) { for(int m = 0 ; m <= n[5] ; ++ m) { if(i < n[1]) f[i+1][j][k][l][m] += f[i][j][k][l][m] ; if(j < n[2] && i > j) f[i][j+1][k][l][m] += f[i][j][k][l][m] ; if(k < n[3] && j > k && i >= j) f[i][j][k+1][l][m] += f[i][j][k][l][m] ; if(l < n[4] && k > l && i >= j && j >= k) f[i][j][k][l+1][m] += f[i][j][k][l][m] ; if(m < n[5] && l > m && i >= j && j >= k && k >= l) f[i][j][k][l][m+1] += f[i][j][k][l][m] ; } } } } } printf("%lld\n",f[n[1]][n[2]][n[3]][n[4]][n[5]]) ; } return 0; }
Kefa and Dishes codeforces 580D
题解：状压dp
代??
#include <bits/stdc++.h> using namespace std; #define ll long long const int maxn = 3e5 + 10 ; ll mp[20][20] ; ll dp[maxn][20] ; ll arr[20] ; int n, m, k ; int main(int argc, char const *argv[]) { ll MAX = -1 ; scanf("%d %d %d",&n,&m,&k) ; for(int i = 1 ; i <= n ; ++ i) scanf("%d",&arr[i]) ; for(int i = 1, u, v, w ; i <= k ; ++ i) { scanf("%d %d %d",&u,&v,&w) ; mp[u][v] = w ; } for(int i = 1 ; i <= n ; ++ i) dp[1<<(i-1)][i] = arr[i] ; for(int s = 0 ; s < (1<<n) ; ++ s) { for(int i = 1 ; i <= n ; ++ i) { int cnt = 0 ; for(int a = 0 ; a < n ; ++ a) if(s&(1<<a)) ++cnt ; if(cnt == m) { //printf("DEBUG %d %d\n",s,i) ; MAX = max(MAX, dp[s][i]) ; continue ; } if( (s&(1<<(i-1))) ) { for(int j = 1 ; j <= n ; ++ j) { if((s & (1<<(j-1))) == 0) { //printf("debug: %d %d %d %d i = %d j = %d\n",dp[s|(1<<(j-1))][j],dp[s][i],mp[i][j],arr[j],i,j) ; dp[s|(1<<(j-1))][j] = max(dp[s|1<<(j-1)][j], dp[s][i] + mp[i][j] + arr[j]) ; } } } } } printf("%lld\n", MAX) ; return 0; }
Yet Another Subarray Problem codeforces 1197D
题解：每隔m分段，然后类似求序列最大子序列的做法
代??
#include <bits/stdc++.h> using namespace std; const int maxn = 3e5 + 10 ; #define ll long long ll arr[maxn] ; ll dp[maxn] ; int n, m, k ; int main(int argc, char const *argv[]) { scanf("%d %d %d",&n,&m,&k) ; arr[0] = 0 ; for(int i = 1 ; i <= n ; ++ i) { scanf("%lld",&arr[i]) ; arr[i] += arr[i - 1] ; } ll ans = 0 ; for(int i = 1 ; i <= n ; ++ i) { for(int j = i ; j >= 1 && j >= i - m + 1 ; -- j) { dp[i] = max(arr[i] - arr[j - 1] - k, dp[i]) ; } if(i - m > 0) { dp[i] = max(dp[i], arr[i] - arr[i - m] + dp[i - m] - k) ; } ans = max(ans, dp[i]) ; } printf("%lld\n",ans) ; return 0 ; }
原文：https://www.cnblogs.com/wifePI/p/12258661.html
