[关闭]
@gzyqwq 2018-10-22T02:33:56.000000Z 字数 10614 阅读 619

DP已经做完的题目：

bzoj 1587

  1. //f[i][j]表示前i个位置,分了j段的最小值.
  2. // f[i][j] = f[l][j - 1] + a[i];
  3. // f[i][j] = min(f[l][j - 1] + sum[i] - sum[l - 1],f[i][j]);
  4. #include <iostream>
  5. #include <cstring>
  6. #include <cstdio>
  7. using namespace std;
  8. const int maxN = 1000 + 7;
  10. inline int read() {
  11.     int x = 0,f = 1;char c = getchar();
  12.     while(c < '0' || c > '9') {if(c == '-')f = -1;c = getchar();}
  13.     while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
  14.     return x * f;
  15. }
  17. int f[maxN][15];//f[i][j]表示前i个东西分成j段的最小价值.
  18. int a[maxN];
  19. int sum[maxN][maxN];//sum[i][j]表示把[1,i - 1]移动到i的价值.
  20. int pre[maxN];
  22. int main() {
  23.     // freopen("1.in","r",stdin);
  24.     int n,k;
  25.     memset(f,0x3f,sizeof(f));
  26.     scanf("%d%d",&n,&k);
  27.     for(int i = n;i >= 1;-- i)
  28.         scanf("%d",&a[i]);
  29.     for(int i = 0;i <= n;++ i) pre[i] = pre[i - 1] + a[i];
  30.     for(int i = 0;i <= n;++ i) 
  31.         for(int j = i + 1;j <= n;++ j) 
  32.             sum[i][j] = sum[i][j - 1] + pre[j - 1] - pre[i - 1];
  33.     f[0][0] = 0;
  34.     for(int i = 1;i <= n;++ i) {
  35.         int tmp = min(i,k);
  36.         for(int j = 1;j <= tmp;++ j) {
  37.             f[i][j] = f[i - 1][j - 1];
  38.             for(int l = 0;l < i;++ l) {
  39.                 f[i][j] = min(f[i][j],f[l - 1][j - 1] + sum[l][i]);
  40.             }
  41.         }   
  42.     }
  43.     printf("%d\n", f[n][k]);
  44.     return 0;
  45. }

luogu 1423

  1. #include <iostream>
  2. #include <cstring>
  3. #include <cstdio>
  4. const int maxN = 100 + 7;
  5. #define rep(i,x,p) for(int i = x;i <= p;++ i) 
  6. #define sep(i,x,p) for(int i = x;i >= p;-- i)
  8. const int gx[] = {0,0,0,1,-1};
  9. const int gy[] = {0,1,-1,0,0};
  11. int a[maxN][maxN];
  12. int f[maxN][maxN];// f[i][j]表示可以到达i行j列的最大步数
  13. int n,m;
  16. inline int read() {
  17.     int x = 0,f = 1;char c = getchar();
  18.     while(c < '0' || c > '9') {if(c == '-')f = -1;c = getchar();}
  19.     while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
  20.     return x * f;
  21. }
  23. inline int max(int a,int b) {return a > b ? a : b;}
  25. int dfs(int x,int y) {
  26.     if(x < 1 || y < 1 || x > n || y > m) return -1;
  27.     if(f[x][y] != -1) return f[x][y];
  28.     int tmp = 0;
  29.     rep(i,1,4)
  30.         if(a[x + gx[i]][y + gy[i]] < a[x][y])tmp = max( dfs(x + gx[i],y + gy[i]) + 1, tmp) ;
  31.     f[x][y] = tmp;
  32.     return tmp;
  33. }
  35. int main() {
  36.     // freopen("1.in","r",stdin);
  37.     n = read();m = read();
  38.     memset(f,-1,sizeof(f));
  39.     rep(i,1,n) 
  40.         rep(j,1,m) 
  41.             a[i][j] = read();
  42.     rep(i,1,n) 
  43.         rep(j,1,m) 
  44.             if(f[i][j] == -1) f[i][j] = dfs(i,j);
  45.     int maxx = 0;
  46.     rep(i,1,n) 
  47.         rep(j,1,n) 
  48.             maxx = max(maxx,f[i][j] + 1);
  49.     printf("%d\n", maxx);
  50.     return 0;
  51. }

bzoj 3208

  1. #include <iostream>
  2. #include <cstdio>
  3. #define rep(i,x,p) for(int i = x;i <= p;++ i)
  4. #define sep(i,x,p) for(int i = x;i >= p;-- i)
  5. const int maxN = 700 + 7;
  6. const int gx[] = {0,0,0,1,-1};
  7. const int gy[] = {0,1,-1,0,0};
  9. int a[maxN][maxN],n,m,f[maxN][maxN];
  10. bool vis[maxN][maxN]; //是否可以移动到这...
  11. char s[2];
  13. inline int read() {
  14.     int x = 0,f = 1;char c = getchar();
  15.     while(c < '0' || c > '9') {if(c == '-')f = -1;c = getchar();}
  16.     while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
  17.     return x * f;
  18. }
  20. inline int max(int a,int b) {return a > b ? a : b;}
  21. inline int min(int a,int b) {return a > b ? b : a;}
  23. void work_1() {
  24.     int x,y,z;
  25.     x = read();y = read();z = read();
  26.     a[x][y] = z;
  27.     return;
  28. }
  30. void work_2() {
  31.     int x1 = read(),y1 = read(),x2 = read(),y2 = read();
  32.     rep(i,x1,x2) 
  33.         rep(j,y1,y2) 
  34.             vis[i][j] = true;
  35.     return;
  36. }
  38. void work_3() {
  39.     int x1 = read(),y1 = read(),x2 = read(),y2 = read();
  40.     rep(i,x1,x2) 
  41.         rep(j,y1,y2) 
  42.             vis[i][j] = false;
  43. }
  45. int dfs(int x,int y) {
  46.     if(x < 1 || y < 1 || x > n || y > n || vis[x][y]) return -1;
  47.     if(f[x][y] != -1) return f[x][y];
  48.     int tmp = 0;
  49.     rep(i,1,4)
  50.         if(a[x + gx[i]][y + gy[i]] < a[x][y])tmp = max( dfs(x + gx[i],y + gy[i]) + 1, tmp) ;
  51.     f[x][y] = tmp;
  52.     return tmp;
  53. }
  55. void work_4() {
  56.     rep(i,1,n) 
  57.         rep(j,1,n)
  58.             f[i][j] = -1;
  59.     rep(i,1,n) 
  60.         rep(j,1,n) 
  61.             if(f[i][j] == -1) f[i][j] = dfs(i,j);
  62.     int maxx = 0;
  63.     rep(i,1,n) 
  64.         rep(j,1,n) 
  65.             maxx = max(maxx,f[i][j] + 1);
  66.     printf("%d\n", maxx);
  67. }
  69. int main()
  70. {
  71.     n = read();
  72.     rep(i,1,n)
  73.         rep(j,1,n)
  74.             a[i][j] = read();
  75.     m = read();
  76.     while(m --) {
  77.         scanf("%s",&s);
  78.         if(s[0] == 'C') work_1();
  79.         if(s[0] == 'S') work_2();
  80.         if(s[0] == 'B') work_3();
  81.         if(s[0] == 'Q') work_4();
  82.     }
  83.     return 0;
  84. }
  85. /*
  86. 并给出m个命令，
  87. C a b c表示坐标为a,b的点的高度改为c；
  88. S a b c d表示左上角为a,b右下角为c,d的矩形地区开始进行保护，
  89. 即不能继续滑雪；
  90. B a b c d表示左上角为a b,右下角为c d的矩形地区取消保护，
  91. 即可以开始滑雪；
  92. Q表示询问现在该风景区可以滑雪的最长路径为多少。对于每个Q要作一次回答。
  93. */

bzoj 1596

  1. #include <iostream>
  2. #include <cstdio>
  3. #define rep(i,x,p) for(int i = x;i <= p;++ i) 
  4. #define sep(i,x,p) for(int i = x;i >= p;-- i) 
  5. const int maxN = 10000 + 7;
  6. const int inf = 0x3f3f3f3f;
  7. using namespace std;
  9. inline int read() {
  10.     int x = 0,f = 1;char c = getchar();
  11.     while(c < '0' || c > '9') {if(c == '-')f = -1;c = getchar();}
  12.     while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
  13.     return x * f;
  14. }
  16. int f[maxN][3]; 
  18. struct Node{
  19.     int v,nex;
  20. }Map[maxN << 1];
  21. int num,head[maxN];
  23. inline void add_Node(int u,int v) {
  24.     Map[++ num].v = v;
  25.     Map[num].nex = head[u];
  26.     head[u] = num;
  27. }
  29. void dfs(int now,int fa) {
  30.     bool flag = false;
  31.     for(int i = head[now];i;i = Map[i].nex) {
  32.         int v = Map[i].v;
  33.         if(v == fa) continue;
  34.         dfs(v,now);
  35.         flag = true;
  36.     }
  37.     if(flag == false) {
  38.         f[now][0] = inf;
  39.         f[now][1] = 1;
  40.         f[now][2] = 0;
  41.         return;
  42.     }
  43.     f[now][1] = 1;
  44.     int tmp_min = inf;
  45.     bool is_ok = true;
  46.     for(int i = head[now];i;i = Map[i].nex) {
  47.         int v = Map[i].v;
  48.         if(v == fa) continue;
  49.         f[now][1] += min(f[v][1] , min ( f[v][0] , f[v][2] ) );
  50.         f[now][2] += min( f[v][0] , f[v][1] );
  51.         tmp_min = min( f[v][1] - f[v][0] , tmp_min);
  52.         if(f[v][1] <= f[v][0]) {
  53.             is_ok = false;
  54.             f[now][0] += f[v][1];
  55.         }
  56.         else f[now][0] += f[v][0];
  57.     }
  58.     if(is_ok) f[now][0] += tmp_min;
  59.     return ;
  60. }
  62. int main()
  63. {
  64.     // freopen("1.in","r",stdin);
  65.     int n,u,v;
  66.     n = read();
  67.     for(int i = 1;i < n;++ i){
  68.         u = read();v = read();
  69.         add_Node(u,v);
  70.         add_Node(v,u);
  71.     }
  72.     dfs(1,1);
  73.     printf("%d\n", min(f[1][0] , f[1][1]));
  74.     return 0;
  75. }
  76. //f[i][0]表示以i为根的子树,最少建造的无线电个数,i点被其儿子覆盖
  77. //f[i][1]表示以i为根的子树,最少建造的无线电个数,i点被自己覆盖
  78. //f[i][2]表示以i为根的子树,最少建造的无线电个数,i点被其父亲覆盖
  79. //f[i][0] = min(   )
  80. //转移方程:
  81. //f[i][0] += f[v][0] , f[v][1] ) ;//一定要有一个.这个真麻烦....无语...莫名无语...
  82. //f[i][1] += min (f[v][2] , f[v][0], f[v][1]) + 1;
  83. //f[i][2] += min ( f[v][0], f[v][1] );

Bzoj 1827

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #define rep(i,x,p) for(re int i = x;i <= p;++ i) 
  5. #define sep(i,x,p) for(re int i = x;i >= p;-- i)
  6. using namespace std;
  7. #define ll long long
  8. #define re register
  9. const int maxN = 100000 + 7;
  11. struct Node {
  12.     int v,nex;
  13.     int w;
  14. }Map[maxN << 1];
  15. int num,head[maxN];
  17. inline int read() {
  18.     int x = 0 ,f = 1;char c = getchar();
  19.     while(c < '0' || c > '9') {if(c == '-')f = -1;c = getchar();}
  20.     while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
  21.     return x * f;
  22. }
  24. inline void add_Node(int u,int v,int w) {
  25.     Map[++ num] = (Node) {v,head[u],w};
  26.     head[u] = num;
  27.     return;
  28. }
  30. ll f[maxN];
  31. ll D[maxN]; 
  32. ll Q[maxN]; 
  34. // f[v] = f[u] + (sum - 2 * D[i]) * w[i];
  35. // D[u] = \sum D[v] + c[u]
  36. // Q[u] = \sum Q[v] + \sum( D[v] * w[i])
  38. void dfs_1(int now,int fa) {
  39.     for(int i = head[now];i;i = Map[i].nex) {
  40.         int v = Map[i].v,w = Map[i].w;
  41.         if(v != fa) {
  42.             dfs_1(v,now);
  43.             D[now] += D[v];
  44.             Q[now] = Q[now] + Q[v] + D[v] * w;
  45.         }
  46.     }
  47.     return;
  48. }
  50. void dfs_2(int now,int fa) {
  51.     for(int i = head[now];i;i = Map[i].nex) {
  52.         int v = Map[i].v,w = Map[i].w;
  53.         if(v != fa) {
  54.             f[v] = f[now] + (D[1] - 2 * D[v]) * w;
  55.             dfs_2(v,now);
  56.         }
  57.     }
  58. }
  60. int main() {
  61. //  freopen("1.in","r",stdin);
  62.     int n = read(),u,v,w;
  63.     rep(i,1,n) D[i] = read();
  64.     rep(i,1,n - 1) {
  65.         u = read();v = read();w = read();
  66.         add_Node(u,v,w);
  67.         add_Node(v,u,w);
  68.     }
  69.     dfs_1(1,1);
  70.     f[1] = Q[1];
  71.     dfs_2(1,1);
  72.     ll ans = 1e12;
  73.     rep(i,1,n) ans = min(ans,f[i]);
  74.     printf("%lld\n", ans);
  75.     return 0;
  76. }

bzoj 1037

  1. #include <iostream>
  2. #include <cstdio>
  3. const int maxN = 150 + 7;
  4. const int maxM = 20 + 7;
  5. #define rep(i,x,p) for(int i = x;i <= p;++ i) 
  6. const int mod = 12345678;
  8. int f[303][153][23][23];//f[i][j][l][k]表示前i个人,有j个男生.l表示以i为后缀的男生-女生的最大值,
  9. //k表示以i为后缀的女生-男生的最大值,
  11. inline int max(int a,int b) {return a > b ? a : b;}
  13. int main() {
  14.     f[0][0][0][0] = 1;
  15.     int n,m,k;
  16.     scanf("%d%d%d",&n,&m,&k);
  17.     rep(i,0,n + m - 1) 
  18.         rep(j,0,n) 
  19.             rep(x,0,k)
  20.                 rep(y,0,k)
  21.                     if(f[i][j][x][y]) {
  22.                         if(j + 1 <= n && x + 1 <= k) f[i + 1][j + 1][x + 1][max(y - 1,0)] = (f[i + 1][j + 1][x + 1][max(y - 1,0)] + f[i][j][x][y] ) % mod;
  23.                         if(i + 1 - j <= m && y + 1 <= k) f[i + 1][j][max(x - 1,0)][y + 1] = f[i + 1][j][max(x - 1,0)][y + 1]  + f[i][j][x][y] % mod;
  24.                     }
  25.     int ans = 0;
  26.     rep(i,0,k)
  27.         rep(j,0,k)
  28.             ans = (ans + f[n + m][n][i][j]) % mod;
  29.     printf("%d\n",ans);       
  31.     return 0;
  32. }
  33. 

bzoj 2037

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. using namespace std;
  6. const int maxN = 1000 + 7;
  8. int f[maxN][maxN][2]; 
  9. int sum[maxN][maxN],tmp_sum;
  11. struct Node {
  12.     int x,y,w;
  13. }Map[maxN];
  15. inline int read() {
  16.     int x = 0,f = 1;char c = getchar();
  17.     while(c < '0' || c > '9') {if(c == '-')f = -1;c = getchar();}
  18.     while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
  19.     return x * f;
  20. }
  22. bool cmp(Node a,Node b) {
  23.     return a.x < b.x;
  24. }
  26. main() {
  27.     int n,c,id;
  28.     n = read();c = read();
  29.     Map[n + 1].x = c; 
  30.     for(int i = 1;i <= n;++ i) 
  31.         scanf("%d",&Map[i].x);
  32.     for(int i = 1;i <= n;++ i) 
  33.         scanf("%d",&Map[i].y);
  34.     for(int i = 1;i <= n;++ i) 
  35.         scanf("%d",&Map[i].w),tmp_sum += Map[i].w;
  36.     sort(Map + 1,Map + n + 2,cmp);
  37.     for(int i = 1;i <= n + 1;++ i) {
  38.         if(c == Map[i].x) id = i;
  39.     }
  40.     for(int i = 1;i <= n + 1;++ i) 
  41.         for(int j = i;j <= n + 1;++ j) 
  42.             sum[i][j] = sum[i][j - 1] + Map[j].w;
  43.     for(int i = 1;i <= n + 1;++ i) 
  44.         for(int j = i;j <= n + 1;++ j) 
  45.             sum[i][j] = tmp_sum - sum[i][j];
  46.     memset(f,-0x3f,sizeof(f));
  47.     f[id][id][1] = f[id][id][0] = 0;
  48.     for(int len = 1;len <= n;++ len) {
  49.         for(int l = 1;l + len <= n + 1;++ l) {
  50.             int r = l + len;
  51.             f[l][r][0] = Map[l].y + max( f[l + 1][r][0] - (Map[l + 1].x - Map[l].x) * sum[l + 1][r] ,f[l + 1][r][1] - ( Map[r].x - Map[l].x ) * sum[l + 1][r]);
  52.             f[l][r][1] = Map[r].y + max( f[l][r - 1][1] - (Map[r].x - Map[r - 1].x) * sum[l][r - 1] ,f[l][r - 1][0] - ( Map[r].x - Map[l].x ) * sum[l][r - 1]);
  53.         }
  54.     }
  55.     printf("%.3lf\n", max(f[1][n + 1][1] , f[1][n + 1][0]) / 1000.0);
  56.     return 0;
  57. }

luogu 1220

  1. #include <iostream>
  2. #include <cstring>
  3. #include <cstdio>
  4. using namespace std;
  5. #define int long long
  6. const int maxN = 1000 + 7;
  8. int f[maxN][maxN][2]; //f[i][j][k]表示i到j区间关闭路灯的最小功耗 k:0在左边 1在右边.
  9. int sum[maxN][maxN],tmp_sum;
  11. struct Node {
  12.     int pos;
  13.     int w;
  14. }Map[maxN];
  16. inline int read() {
  17.     int x = 0,f = 1;char c = getchar();
  18.     while(c < '0' || c > '9') {if(c == '-')f = -1;c = getchar();}
  19.     while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
  20.     return x * f;
  21. }
  23. main() {
  24.     int n,c;
  25.     n = read();c = read();
  26.     for(int i = 1;i <= n;++ i) 
  27.         scanf("%d%lld",&Map[i].pos,&Map[i].w),tmp_sum += Map[i].w;
  28.     for(int i = 1;i <= n;++ i) 
  29.         for(int j = i;j <= n;++ j) 
  30.             sum[i][j] = sum[i][j - 1] + Map[j].w;
  31.     for(int i = 1;i <= n;++ i) 
  32.         for(int j = i;j <= n;++ j) 
  33.             sum[i][j] = tmp_sum - sum[i][j];
  34.     memset(f,1,sizeof(f));
  35.     f[c][c][1] = f[c][c][0] = 0;
  36.     for(int len = 1;len < n;++ len) {
  37.         for(int l = 1;l + len<= n;++ l) {
  38.             int r = l + len;
  39.             f[l][r][0] = min( f[l + 1][r][0] + (Map[l + 1].pos - Map[l].pos) * sum[l + 1][r] ,f[l + 1][r][1] + ( Map[r].pos - Map[l].pos ) * sum[l + 1][r]);
  40.             f[l][r][1] = min( f[l][r - 1][1] + (Map[r].pos - Map[r - 1].pos) * sum[l][r - 1] ,f[l][r - 1][0] + ( Map[r].pos - Map[l].pos ) * sum[l][r - 1]);
  41.         }
  42.     }
  43.     printf("%lld\n", min(f[1][n][1] , f[1][n][0]));
  44.     return 0;
  45. }

bzoj4033

  1. /*
  2. 边一侧的黑节点数*另一侧的黑节点数*边权+一侧的白节点数*另一侧的白节点数*边权
  3. */
  4. #include <iostream>
  5. #include <cstdio>
  6. #define rep(i,x,p) for(int i = x;i <= p;++ i) 
  7. #define sep(i,x,p) for(int i = x;i >= p;-- i)
  8. #define int long long
  9. const int maxN = 2000 + 7;
  11. struct Node {
  12.     int v,nex,w;
  13. }Map[maxN << 1];
  14. int f[maxN][maxN];
  15. int head[maxN],num;
  16. int size[maxN];
  18. inline int read() {
  19.     int x = 0,f = 1;char c = getchar();
  20.     while(c < '0' || c > '9') {if(c == '-')f = -1;c = getchar();}
  21.     while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
  22.     return x * f;
  23. }
  25. void add_Node(int u,int v,int w) {
  26.     Map[++ num] = (Node) {v,head[u],w};
  27.     head[u] = num;
  28.     return;
  29. }
  31. int n,k;
  32. inline int max(int a,int b) {return a > b ? a : b;}
  34. int calc(int val,int num,int x)//计算这条边的贡献 
  35. {
  36.     val=val * x * (k - x) + val * (num - x) * (n - k - (num - x));
  37.     return val;
  38. }
  40. void DP(int now,int fa) {
  41.     size[now] = 1;
  42.     for(int i = head[now];i;i = Map[i].nex) {
  43.         int v = Map[i].v;
  44.         if(v == fa) continue;
  45.         DP(v,now);
  46.         sep(j , size[now], 0) {
  47.             sep(l , size[v], 0) {
  48.                 int tmp = f[now][j] + f[v][l] + calc(Map[i].w,size[v],l);
  49.                 f[now][j + l] = max(f[now][j + l] , tmp);
  50.             }   
  51.         }   
  52.         size[now] += size[v];
  53.     }
  54. }
  55. #undef int 
  57. int main() {
  58.     #define int long long
  59.     scanf("%lld%lld",&n,&k);
  60.     int u , v, w;
  61.     rep(i,1,n - 1) {
  62.         u = read();v = read();w = read();
  63.         add_Node(u,v,w);
  64.         add_Node(v,u,w);
  65.     }
  66.     DP(1,1);
  67.     printf("%lld\n", f[1][k]);
  68.     return 0;
  69. }

luogu 3174

bzoj 1260

  1. /*
  2. 卡常记录: 28ms -> 30ms ?????
  3. 反过来考虑
  4. f[i][j]表示i~j被染色的最小次数.
  5. 分为三种情况考虑:
  6. 1.l == r f[l][r] = 1;
  7. 2.s[l] == s[r] f[l][r] = min(f[i + 1][r] , f[l][r - 1])
  8. 3.不满足上述条件的话.
  9. 枚举断点即可.
  10. */
  11. #include <iostream>
  12. #include <cstring>
  13. #include <cstring>
  14. #include <cstdio>
  15. #define rep(i,x,p) for(register int i = x;i <= p;++ i) 
  16. #define sep(i,x,p) for(register int i = x;i >= p;-- i)
  17. const int maxN = 50 + 7;
  18. using namespace std;
  20. char s[maxN];
  21. int f[maxN][maxN];
  23. int main() {
  24.     scanf("%s",s + 1);
  25.     int n = strlen(s + 1);
  26.     memset(f,0x3f,sizeof(f));
  27.     rep(i,1,n) f[i][i] = 1;
  28.     rep(len,1,n - 1) {
  29.         for(register int l = 1;l + len <= n;++ l){
  30.             int r = l + len;
  31.             if(s[l] == s[r]) f[l][r] = min(f[l + 1][r] , f[l][r - 1]);
  32.             rep(k , l ,r - 1)  f[l][r] = min(f[l][k] + f[k + 1][r],f[l][r]);
  33.         }
  34.     }
  35.     printf("%d", f[1][n]);
  36.     return 0;
  37. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注