博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
黑书上的DP例题
阅读量：4309 次
发布时间：2019-06-06

本文共 21928 字，大约阅读时间需要 73 分钟。

page section no title submit
113 1.5.1 例题1 括号序列
116 1.5.1 例题2 棋盘分割
117 1.5.1 例题3 决斗
117 1.5.1 例题4 “舞蹈家”怀特先生
119 1.5.1 例题5 积木游戏
123 1.5.2 例题1 方块消除
123 1.5.2 例题2 公路巡逻
125 1.5.2 例题3 并行期望值 POJ1074
131 1.5.2 例题6 不可分解的编码 http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2475
133 1.5.2 例题7 青蛙的烦恼
135 1.5.2 例题9 最优排序二叉树 http://judge.noi.cn/problem?id=1059
138 1.5.2 例题10 Bugs公司 POJ1038
139 1.5.2 例题11 迷宫统计 http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=70&page=show_problem&problem=1472
142 1.5.2 例题12 贪吃的九头龙 http://judge.noi.cn/problem?id=1043
151 1.5.3 问题2 最长上升子序列问题 http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=17&page=show_problem&problem=1475
151 1.5.3 问题3 最优二分检索树 http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=15&page=show_problem&problem=1245
152 1.5.3 问题4 任务调度问题 POJ1180
121 1.5.1 1.5.8 艺术馆的火灾 http://221.192.240.23:9088/showproblem?problem_id=1366
144 1.5.2 1.5.10 快乐的蜜月 http://judge.noi.cn/problem?id=1052
145 1.5.2 1.5.12 佳佳的筷子 http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1212
146 1.5.2 1.5.13 偷懒的工人 POJ1337
146 1.5.2 1.5.15 平板涂色 POJ1691
147 1.5.2 1.5.16 道路重建 POJ1947
147 1.5.2 1.5.17 圆和多边形 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1679
148 1.5.2 1.5.18 Jimmy落地 POJ1661
148 1.5.2 1.5.19 免费糖果 http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1059
157 1.5.3 1.5.22 回文词 POJ1159
157 1.5.3 1.5.24 邮局 POJ1160
158 1.5.3 1.5.26 奶牛转圈 POJ1946
158 1.5.3 1.5.27 元件折叠 http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1180

现在开始训练一下DP:

递归动机的DP：

pku 1141 

黑书上讲的第一个题目,题意就给出一个括号序列，包含有"(" ")" "[" "]" 求最少添加的括号数是的最终的序列是合法的并输出这个序列。

思路：

首先这里求解的话要使用递归的思路，这是动态规划产生的第一种动机，于是我们可以写出记忆化搜索。进行求解。

dp[l][r] = min(dp[l][r],dp[l + 1][r - 1])如果s[l]与s[r]匹配的话。

否则我们就将该序列分成两段分别求解（这也是求解DP线性模型的一种递归分解思路）

dp[l][r] = min(dp[l][r],dp[l][k] + dp[k + 1][r])

这里关键是怎么讲可行解输出呢？开始我是通过比较dp[l][r] 与 dp[l + 1][r  -1] dp[l][k] + dp[k + 1][r]来判断的后来发现这样不对的 如果dp[l + 1][r - 1] = dp[l][k] + dp[k + 1][r]的话就会出现错误，而我们这里dp[l][r]确实从dp[l][k] + dp[k + 1][r]来的。所以，我们要另开一个二维数组记录每种最优状态的来源点。然后再递归的输出即可。

View Code 
#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  #include 
                   
                    #define CL(arr, val) memset(arr, val, sizeof(arr))#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define ll __int64#define L(x) (x) << 1#define R(x) (x) << 1 | 1#define MID(l, r) (l + r) >> 1#define Min(x, y) (x) < (y) ? (x) : (y)#define Max(x, y) (x) < (y) ? (y) : (x)#define E(x) (1 << (x))#define iabs(x) (x) < 0 ? -(x) : (x)#define OUT(x) printf("%I64d\n", x)#define lowbit(x) (x)&(-x)#define Read() freopen("din.txt", "r", stdin)#define Write() freopen("dout.txt", "w", stdout);#define M 137#define N 115using namespace std;const int inf = 0x7f7f7f7f;const int mod = 1000000007;int dp[N][N];char s[N];int mk[N][N];bool cmp(char a,char b){ if ((a == '(' && b == ')') || (a == '[' && b == ']')) return true; return false;}int dfs_DP(int l,int r){ int k; if (l > r) return 0; if (l == r) return (dp[l][r] = 1); if (dp[l][r] != inf) return dp[l][r]; if (cmp(s[l],s[r])) { if (l + 1 == r) { dp[l][r] = 0; mk[l][r] = -1; } else { dfs_DP(l + 1,r - 1); if (dp[l][r] > dp[l + 1][r - 1]) { dp[l][r] = dp[l + 1][r - 1]; mk[l][r] = -1; } // dp[l][r] = min(dp[l][r],dfs_DP(l + 1,r - 1));// printf(">>>**%d %d %d %d\n",l,r,dp[l][r],dp[l + 1][r - 1]); } } for (k = l; k <= r - 1; ++k) { dfs_DP(l,k); dfs_DP(k + 1,r); if (dp[l][r] > dp[l][k] + dp[k + 1][r]) { dp[l][r] = dp[l][k] + dp[k + 1][r]; mk[l][r] = k; }// dp[l][r] = min(dp[l][r],dfs_DP(l,k) + dfs_DP(k + 1,r)); } return dp[l][r];}void print(int l,int r){ if (l > r) return; if (l == r) { if (s[l] == '(' || s[l] == ')') printf("()"); else if (s[l] == '[' || s[l] == ']') printf("[]"); return; } if (cmp(s[l],s[r]) && mk[l][r] == -1) { printf("%c",s[l]); print(l + 1,r - 1); printf("%c",s[r]); } else { print(l,mk[l][r]); print(mk[l][r] + 1,r); }}int main(){// Read();// Write(); int i,j; scanf("%s",s); int n = strlen(s); CL(mk,-1); for (i = 0; i <= n; ++i) { for (j = 0; j <= n; ++j) { dp[i][j] = inf; } } dfs_DP(0,n - 1);// printf("%d\n",dp[0][n - 1]); print(0,n - 1); printf("\n"); return 0;}

 

 pku 1191 

思路：

棋盘横着切竖着切，然后递归将棋盘不断缩小到能够求解的状态。记忆化搜索。这里中间计算值可能会超0x7f7f7f7f，所以最大值取大一点。这里让哥条了很长时间。。

View Code 
#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  #include 
                   
                    #define CL(arr, val) memset(arr, val, sizeof(arr))#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define ll __int64#define L(x) (x) << 1#define R(x) (x) << 1 | 1#define MID(l, r) (l + r) >> 1#define Min(x, y) (x) < (y) ? (x) : (y)#define Max(x, y) (x) < (y) ? (y) : (x)#define E(x) (1 << (x))#define iabs(x) (x) < 0 ? -(x) : (x)#define OUT(x) printf("%I64d\n", x)#define lowbit(x) (x)&(-x)#define Read() freopen("din.txt", "r", stdin)#define Write() freopen("dout.txt", "w", stdout);#define M 137#define N 10using namespace std;const int inf = 0x7f7f7f7f;const int mod = 1000000007;int mat[N][N];int s[N][N][N][N];int dp[N][N][N][N][20];ll map[N][N];int n;int DP(int x1,int y1,int x2,int y2,int no){ int x,y; if (no == 1) return dp[x1][y1][x2][y2][no]; if (dp[x1][y1][x2][y2][no] != -1) return dp[x1][y1][x2][y2][no]; int ans = 999999999; for (x = x1; x < x2; ++x) { ans = min(ans,min(DP(x1,y1,x,y2,no - 1) + s[x + 1][y1][x2][y2],DP(x + 1,y1,x2,y2,no - 1) + s[x1][y1][x][y2])); } for (y = y1; y < y2; ++y) { ans = min(ans,min(DP(x1,y1,x2,y,no - 1) + s[x1][y + 1][x2][y2],DP(x1,y + 1,x2,y2,no - 1) + s[x1][y1][x2][y])); } return (dp[x1][y1][x2][y2][no] = ans);}int main(){// Read(); int i,j; scanf("%d",&n); int sum = 0; for (i = 1; i <= 8; ++i) { for (j = 1; j <= 8; ++j) { scanf("%d",&mat[i][j]); sum += mat[i][j]; } } CL(s,0); CL(dp,-1); int x1,y1,x2,y2; for (x1 = 1; x1 <= 8; ++x1) { for (y1 = 1; y1 <= 8; ++y1) { for (x2 = x1; x2 <= 8; ++x2) { for (y2 = y1; y2 <= 8; ++y2) {// printf("%d %d %d %d\n",x1,y1,x2,y2); for (i = x1; i <= x2; ++i) { for (j = y1; j <= y2; ++j) { s[x1][y1][x2][y2] += mat[i][j]; } } s[x1][y1][x2][y2] *= s[x1][y1][x2][y2]; dp[x1][y1][x2][y2][1] = s[x1][y1][x2][y2]; } } } } DP(1,1,8,8,n); double ans = (1.0*dp[1][1][8][8][n])/(1.0*n) - (1.0*sum*sum)/(1.0*n*n); printf("%.3f\n",sqrt(ans)); return 0;}

 

 sicily 1822 

题意：黑书

思路：

开始吧题意理解错了，一位如果判断i必须从i开始一次与i + 1,i +２比较呢。ＳＢ了。。

dp[i][j]表示i能否与j相遇，记住这里是相遇不表示i与j谁能打败谁。如果判断x点，我们把x点查分为x与n + 1,这样讲原来的环转化成连，然后求x与n +1是否能够相遇即可

dp[i][j] = (dp[i][k] && dp[k][j] && (mat[i][k],mat[j][k])),mat[i][j]表示i能否打败j

View Code 
#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  #include 
                   
                    #define CL(arr, val) memset(arr, val, sizeof(arr))#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define ll __int64#define L(x) (x) << 1#define R(x) (x) << 1 | 1#define MID(l, r) (l + r) >> 1#define Min(x, y) (x) < (y) ? (x) : (y)#define Max(x, y) (x) < (y) ? (y) : (x)#define E(x) (1 << (x))#define iabs(x) (x) < 0 ? -(x) : (x)#define OUT(x) printf("%I64d\n", x)#define lowbit(x) (x)&(-x)#define Read() freopen("din.txt", "r", stdin)#define Write() freopen("dout.txt", "w", stdout);#define M 137#define N 50using namespace std;const int inf = 0x7f7f7f7f;const int mod = 1000000007;int mat[N][N];int dp[N][N];int seq[N];bool vt[N][N];int n;int DP(int l,int r){ int k; if (vt[l][r]) return dp[l][r]; for (k = l + 1; k <= r - 1; ++k) { dp[l][r] = (DP(l,k)&&DP(k,r)&&(mat[seq[l]][seq[k]] || mat[seq[r]][seq[k]])); if (dp[l][r]) break; } vt[l][r] = true; return dp[l][r];}int main(){// Read(); int T,i,j; scanf("%d",&T); while (T--) { scanf("%d",&n); CL(mat,0); for (i = 1; i <= n; ++i) for (j = 1; j <= n; ++j) scanf("%d",&mat[i][j]); for (i = 1; i <= n; ++i) { CL(dp,0); CL(vt,false); int pos = (i - 1); if (pos == 0) pos = n; int ln = 0; for (j = i; j <= n; ++j) seq[++ln] = j; for (j = 1; j <= i - 1; ++j) seq[++ln] = j; seq[++ln] = n + 1; for (j = 1; j <= n; ++j) { dp[j][j + 1] = dp[j + 1][j] = 1; vt[j][j + 1] = vt[j + 1][j] = true; } DP(1,ln); if (dp[1][ln]) printf("1\n"); else printf("0\n"); }// if (T != 0) printf("\n"); } return 0;}

 

hdu 3632 

题意：

这题和上题目意思一样，只不过这里是序列1-n然后每个人可以选择左右两边的人进行对决，我刚开始看到这题目的时候，就以为是上边那道题目，结果样例过了，就是不对。

思路：

这里某个人i如果能够胜出,那么他一定能够和0点并且和n + 1点相遇。（与上题一样，抽象出来的两个点）。然后我们只要枚举任意两点是否能够相遇即可，

dp[i][j] = (dp[i][k] && dp[k][j] && (mat[i][k],mat[j][k])),mat[i][j]表示i能否打败j,   这里根据i到j的距离进行递推的。

View Code 
#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  #include 
                   
                    #define CL(arr, val) memset(arr, val, sizeof(arr))#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define ll __int64#define L(x) (x) << 1#define R(x) (x) << 1 | 1#define MID(l, r) (l + r) >> 1#define Min(x, y) (x) < (y) ? (x) : (y)#define Max(x, y) (x) < (y) ? (y) : (x)#define E(x) (1 << (x))#define iabs(x) (x) < 0 ? -(x) : (x)#define OUT(x) printf("%I64d\n", x)#define lowbit(x) (x)&(-x)#define Read() freopen("din.txt", "r", stdin)#define Write() freopen("dout.txt", "w", stdout);#define M 30007#define N 117using namespace std;const int inf = 100000007;const int mod = 1000000007;int val[N];int mat[N][N];int n;int dp[N][N];bool vt[N][N];bool isok(int i,int j,int k){ if (dp[i][k] && dp[k][j] && (mat[i][k] || mat[j][k])) return true; else return false;}int main(){// Read(); int T,i,j; int cas = 1; scanf("%d",&T); while (T--) { scanf("%d",&n); for (i = 1; i <= n; ++i) scanf("%d",&val[i]); CL(mat,0);//记住要初始化 for (i = 1; i <= n; ++i) for (j = 1; j <= n; ++j) scanf("%d",&mat[i][j]); CL(dp,0); for (i = 0; i <= n + 1; ++i) dp[i][i + 1] = dp[i + 1][i] = 1; int k,p; for (k = 2; k <= n; ++k)//递推策略 { for (i = 0; i + k <= n + 1; ++i) { j = i + k; for (p = i + 1; p <= j - 1; ++p) { if (isok(i,j,p)) { dp[i][j] = 1; } } } } int ans = 0; for (i = 1; i <= n; ++i) { if (dp[0][i] && dp[i][n + 1] && val[i] > ans) ans = val[i]; //i能否杀到0并且能够杀到n + 1 } printf("Case %d: %d\n",cas++,ans); } return 0;}

 

题意：看给书吧..

思路：

我们考虑的是最后一段是单独消去还是和前边的一起消去，这样就可以构造出递归的递推式了。

题目的方块可以表示称color[i],len[i],1<=i<=l

这里l表示有多少"段"不同的颜色方块
color[i]表示第i段的颜色,len[i]表示第i段的方块长度
让f[i,j,k]表示把(color[i],len[i]),(color[i+1],len[i+1]),...,(color[j-1],len[j-1]),(color[j],len[j]+k)合并的最大得分
考虑(color[j],len[j]+k)这一段,要不马上消掉,要不和前面的若干段一起消掉
1.如果马上消掉,就是f[i,j-1,0]+(len[j]+k)^2
2.如果和前面的若干段一起消,可以假设这"若干段"中最后一段是p,则此时的得分是f[i,p,k+len[j]]+f[p+1,j-1,0]
于是f[i,j,k] = max{ f[i,j-1,0]+(len[j]+k)^2, f[i,p,k+len[j]]+f[p+1,j-1,0] 

View Code 
#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  #include 
                   
                    #include 
                    
                     #define CL(arr, val) memset(arr, val, sizeof(arr))#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define ll long long#define L(x) (x) << 1#define R(x) (x) << 1 | 1#define MID(l, r) (l + r) >> 1#define Min(x, y) (x) < (y) ? (x) : (y)#define Max(x, y) (x) < (y) ? (y) : (x)#define E(x) (1 << (x))#define iabs(x) (x) < 0 ? -(x) : (x)#define OUT(x) printf("%I64d\n", x)#define lowbit(x) (x)&(-x)#define Read() freopen("din.txt", "r", stdin)#define Write() freopen("dout.txt", "w", stdout);#define M 137#define N 207using namespace std;const int inf = 0x7f7fffff;const ll mod = 1000000007;int dp[N][N][N];int a[N],of[N],b[N];int n,ln;int q_DP(int l,int r,int k){ int p; if (dp[l][r][k] != 0) return dp[l][r][k]; if (l == r) { return (dp[l][r][k] = (b[r] + k)*(b[r] + k)); } int ans = 0; ans = max(ans,q_DP(l,r - 1,0) + (b[r] + k)*(b[r] + k)); for (p = l; p + 1 <= r - 1; ++p) { if (of[r] == of[p]) ans = max(ans,q_DP(l,p,k + b[r]) + q_DP(p + 1,r - 1,0)); } return dp[l][r][k] = ans;}int main(){// Read(); int i; int T,cas = 1; scanf("%d",&T); while (T--) { scanf("%d",&n); ln = 0; CL(a,0); for (i = 0; i < n; ++i) { scanf("%d",&a[i]); } ln = 0; int ct = 0; for (i = 0; i < n; ++i) { if (a[i] != a[i + 1]) { b[++ln] = ct + 1; of[ln] = a[i]; ct = 0; } else ct++; }// b[++ln] = ct;// of[ln] = a[n - 1]; CL(dp,0); q_DP(1,ln,0); printf("Case %d: %d\n",cas++,dp[1][ln][0]); } return 0;}

 

 

 

 

 多决策动机的DP:

题意：黑书。。

思路：

这里每一步要么走左腿，要么走右腿，要么原地不动。DFS求解肯定超时，因为状态数太多，所以我们只好利用DP记录所有状态，然后通过每一步的决策。求解所有满足条件的状态。

View Code 
#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  #include 
                   
                    #define CL(arr, val) memset(arr, val, sizeof(arr))#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define ll __int64#define L(x) (x) << 1#define R(x) (x) << 1 | 1#define MID(l, r) (l + r) >> 1#define Min(x, y) (x) < (y) ? (x) : (y)#define Max(x, y) (x) < (y) ? (y) : (x)#define E(x) (1 << (x))#define iabs(x) (x) < 0 ? -(x) : (x)#define OUT(x) printf("%I64d\n", x)#define lowbit(x) (x)&(-x)#define Read() freopen("din.txt", "r", stdin)#define Write() freopen("dout.txt", "w", stdout);#define M 137#define N 10017using namespace std;const int inf = 0x7f7fffff;const int mod = 1000000007;int a[N];int dp[5][5][3];int getS(int x,int y){ if (x == 0) return 2; else if (x == y) return 1; else if (abs(x - y) == 2) return 4; else return 3;}int main(){// Read(); int i,j,k; int n; a[0] = 0; while (~scanf("%d",&a[1])) { if (a[1] == 0) break; i = 2; while (scanf("%d",&a[i])) { if (a[i] == 0) break; i++; } n = i - 1; for (i = 0; i <= 4; ++i) { for (j = 0; j <= 4; ++j) { for (k = 0; k <= 1; ++k) dp[i][j][k] = inf; } } dp[0][0][0] = 0; int u = 0, v = 1; for (k = 0; k < n; ++k) { for (i = 0; i <= 4; ++i) { for (j = 0; j <= 4; ++j) { if (dp[i][j][u] != inf) { if (a[k + 1] != j) //保证左右脚不能在一起 dp[a[k + 1]][j][v] = min(dp[a[k + 1]][j][v],dp[i][j][u] + getS(i,a[k + 1])); if (i != a[k + 1]) dp[i][a[k + 1]][v] = min(dp[i][a[k + 1]][v],dp[i][j][u] + getS(j,a[k + 1])); } } } swap(u,v); //滚动数组优化 for (i = 0; i <= 4; ++i) { for (j = 0; j <= 4; ++j) { dp[i][j][v] = inf; } } } int ans = inf; for (i = 0; i <= 4; ++i) { if (i != a[n]) ans = min(dp[i][a[n]][u],ans); } for (j = 0; j <= 4; ++j) { if (j != a[n]) ans = min(dp[a[n]][j][u],ans); } printf("%d\n",ans); } return 0;}

 

题意：。。。

思路：

就是按着黑书上的第一种思路做的，这里有个地方卡了一下， 就是j表示的类成了j堆，在枚举的时候不能只到m-1否则最后累到第m的堆的最后一个也就不存在了，。

View Code 
#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  #include 
                   
                    #include 
                    
                     #define CL(arr, val) memset(arr, val, sizeof(arr))#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define ll long long#define L(x) (x) << 1#define R(x) (x) << 1 | 1#define MID(l, r) (l + r) >> 1#define Min(x, y) (x) < (y) ? (x) : (y)#define Max(x, y) (x) < (y) ? (y) : (x)#define E(x) (1 << (x))#define iabs(x) (x) < 0 ? -(x) : (x)#define OUT(x) printf("%I64d\n", x)#define lowbit(x) (x)&(-x)#define Read() freopen("din.txt", "r", stdin)#define Write() freopen("dout.txt", "w", stdout);#define M 137#define N 107using namespace std;const int inf = 0x7f7fffff;const ll mod = 1000000007;int dp[N][N][N][4];bool vt[N][N][N][4];int a[N][4][4];int n,m;bool over(int i,int x,int j,int y){ int sda = max(a[i][x][0],a[i][x][1]); int sdb = min(a[i][x][0],a[i][x][1]); int pda = max(a[j][y][0],a[j][y][1]); int pdb = min(a[j][y][0],a[j][y][1]); if (sda <= pda && sdb <= pdb) return true; else return false;}int main(){// Read(); int i,j,k,p,q; int x,y,z; scanf("%d%d",&n,&m); CL(a,0); for (i = 1; i <= n; ++i) { scanf("%d%d%d",&x,&y,&z); //表示第i个面的的长宽高 a[i][0][0] = x; a[i][0][1] = y; a[i][0][2] = z; a[i][1][0] = y; a[i][1][1] = z; a[i][1][2] = x; a[i][2][0] = z; a[i][2][1] = x; a[i][2][2] = y; } CL(dp,0); CL(vt,false); vt[0][0][0][0] = true; for (i = 0; i < n; ++i) { for (j = 0; j <= min(i,m); ++j) { for (k = 0; k <= i; ++k) { for (p = 0; p < 3; ++p) { if (vt[i][j][k][p]) { for (q = 0; q < 3; ++q) { //可以累加 if (over(i + 1,q,k,p)) { dp[i + 1][j][i + 1][q] = max(dp[i + 1][j][i + 1][q],dp[i][j][k][p] + a[i + 1][q][2]); vt[i + 1][j][i + 1][q] = true; } //另起一堆 dp[i + 1][j + 1][i + 1][q] = max(dp[i + 1][j + 1][i + 1][q],dp[i][j][k][p] + a[i + 1][q][2]); vt[i + 1][j + 1][i + 1][q] = true; //直接跳过 dp[i + 1][j][k][p] = max(dp[i + 1][j][k][p],dp[i][j][k][p]); vt[i + 1][j][k][p] = true;// printf(">>>>%d %d %d\n",dp[i + 1][j][i + 1][q],dp[i + 1][j + 1][i + 1][q],dp[i + 1][j][k][p]); } } } } } } int ans = 0;// printf("%d %d\n",n,m); for (k = 1; k <= n; ++k) { for (p = 0; p < 3; ++p) {// printf(">>>>>>%d\n",dp[n][m][k][p]); ans = max(ans,dp[n][m][k][p]); } } printf("%d\n",ans); return 0;}

 

思路：

dp[i][j]表示到达在时间为j时第i个关口与巡逻车相遇的最少次数 dp[i + 1][j + 1] = max(dp[i + 1][j + 1],dp[i][j] + s); s表示目标车在 [j, j + k]时间段内从第i个关口出发到i + 1个关口与巡逻车相遇的次数。

其实状态转移很好想，只是在车辆相遇上脑子短路了，我们只要排除不相遇的就好了。

这里还没有优化。。

View Code 
#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  #include 
                   
                    #define CL(arr, val) memset(arr, val, sizeof(arr))#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define ll long long#define L(x) (x) << 1#define R(x) (x) << 1 | 1#define MID(l, r) (l + r) >> 1#define Min(x, y) (x) < (y) ? (x) : (y)#define Max(x, y) (x) < (y) ? (y) : (x)#define E(x) (1 << (x))#define iabs(x) (x) < 0 ? -(x) : (x)#define OUT(x) printf("%I64d\n", x)#define lowbit(x) (x)&(-x)#define Read() freopen("din", "r", stdin)#define Write() freopen("dout", "w", stdout);#define M 86405#define N 55using namespace std;const int inf = 0x7f7f7f7f;const int mod = 1000000007;struct node{ int s,e;}nd[N][N];int ln[N];int dp[N][M];bool vt[N][M];int n,m;int main(){// Read(); int i,j,k; int ni,di; char ti[7]; scanf("%d%d",&n,&m); CL(ln,0); CL(nd,0); for (j = 0; j < m; ++j) { scanf("%d%s%d",&ni,ti,&di); int no = 0; int sum = 0; for (i = 0; i < 6; ++i) { if (i%2 == 1) { no = no*10 + ti[i] - '0'; int tmp = 0; if (i == 1) tmp = 3600; else if (i == 3) tmp = 60; else tmp = 1; sum += no*tmp; no = 0; } else { no = no*10 + ti[i] - '0'; } } int &p = ln[ni]; nd[ni][p].s = sum; nd[ni][p].e = sum + di; p++; } for (i = 1; i <= n; ++i) { for (j = 0; j <= 86400; ++j) { dp[i][j] = inf; } } CL(vt,false); dp[1][21600] = 0; vt[1][21600] = true; for (i = 1; i < n; ++i) { for (j = 21600; j <= 51000; ++j) { if (vt[i][j]) { for (k = 300; k <= 600; ++k) { int s = 0; int p; for (p = 0; p < ln[i]; ++p) { if (nd[i][p].e == j + k) s++; else { if (j <= nd[i][p].s && j + k <= nd[i][p].e) continue; if (j >= nd[i][p].s && j + k >= nd[i][p].e) continue; s++; } } dp[i + 1][j + k] = min(dp[i + 1][j + k],dp[i][j] + s); vt[i + 1][j + k] = true; } } } } int ans = inf; int tim = 0; for (i = 21600; i <= 51000; ++i) { if (vt[n][i] && dp[n][i] < ans) { ans = dp[n][i]; tim = i; } } int hh = tim/3600; tim -= hh*3600; int mm = tim/60; tim -= mm*60; int ss = tim; printf("%d\n%02d%02d%02d\n",ans,hh,mm,ss); return 0;}

 

 ===================================================================

 

poj 1337 

题意：

一个懒工人，他想工作的时间尽量少。有N个任务，每个任务有开始时间和deadline，工人完成这个工作需要ti时间。如果某个时刻有工作可以做（这里是说，如果从这个时刻开始某个工作，在deadline之前能够完成)，那么这个工人必须做，但是如果这个时刻存在着多余1件工作可以做，工人可以选择；假设这个时刻没有工作可以做了，工人就可以偷懒直到有新的任务到来

思路：

刚开始以为只要我一空下来有工作，我就必须从这一点开始工作来着，其实不是的，只要在最晚期限之前完成该工作即可。

dp[i]表示在时间点i时，完成工作所需要的最少时间，dp[i + 1] = min(dp[i + 1],dp[i])当该时间没有工作干时，当有多个工作时，dp[i + tk] = min(dp[i + tk],dp[i] + tk) k表示第k个工作可以再时间点i完成

这里注意inf = 0x3fffffff 因为会有inf的相加，这里快整死我了，给很长时间没有条出来。。

View Code 
#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  #include 
                   
                    #include 
                    
                     #define CL(arr, val) memset(arr, val, sizeof(arr))#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define ll long long#define L(x) (x) << 1#define R(x) (x) << 1 | 1#define MID(l, r) (l + r) >> 1#define Min(x, y) (x) < (y) ? (x) : (y)#define Max(x, y) (x) < (y) ? (y) : (x)#define E(x) (1 << (x))#define iabs(x) (x) < 0 ? -(x) : (x)#define OUT(x) printf("%I64d\n", x)#define lowbit(x) (x)&(-x)#define Read() freopen("din.txt", "r", stdin)#define Write() freopen("dout.txt", "w", stdout);#define M 107#define N 117using namespace std;const ll mod = 1000000007;const int inf = 0x3fffffff;struct node{ int ti,ai,di;}nd[N];int dp[260];vector
                     
                       work[260];int main(){// Read();// printf("%d \n%d\n",0x7fffffff,0x3fffffff); int T; int i,j; int n; scanf("%d",&T); while (T--) { scanf("%d",&n); int s = inf, e = 0; for (i = 0; i < n; ++i) { scanf("%d%d%d",&nd[i].ti,&nd[i].ai,&nd[i].di); s = min(s,nd[i].ai); e = max(e,nd[i].di); } for (i = s; i <= e; ++i) { work[i].clear(); for (j = 0; j < n; ++j) { if (i >= nd[j].ai && i + nd[j].ti <= nd[j].di) { work[i].push_back(j); } } } for (i = s; i <= e; ++i) dp[i] = inf; dp[s] = 0; for (i = s; i < e; ++i) { if (work[i].size() == 0) dp[i + 1] = min(dp[i + 1],dp[i]); else { int sz = work[i].size(); for (int j = 0; j < sz; ++j) { int k = work[i][j]; dp[i + nd[k].ti] = min(dp[i + nd[k].ti],dp[i] + nd[k].ti); } } } printf("%d\n",dp[e]); } return 0;}

 

 

 

 

转载于:https://www.cnblogs.com/E-star/archive/2013/04/15/3022391.html

你可能感兴趣的文章
CentOS Docker 安装
查看>>
Nginx
查看>>
Navicat远程连接云主机数据库
查看>>
Nginx配置文件nginx.conf中文详解（总结）
查看>>
Mysql出现Table 'performance_schema.session_status' doesn't exist
查看>>
MySQL innert join、left join、right join等理解
查看>>
vivado模块封装ip/edf
查看>>
sdc时序约束
查看>>
Xilinx Jtag Access/svf文件/BSCANE2
查看>>
NoC片上网络
查看>>
开源SoC整理
查看>>
【2020-3-21】Mac安装Homebrew慢，解决办法
查看>>
influxdb 命令行输出时间为 yyyy-MM-dd HH:mm:ss(年月日时分秒)的方法
查看>>
已知子网掩码，确定ip地址范围
查看>>
判断时间或者数字是否连续
查看>>
docker-daemon.json各配置详解
查看>>
Docker(一）使用阿里云容器镜像服务
查看>>
Docker(三） 构建镜像
查看>>
FFmpeg 是如何实现多态的？
查看>>
FFmpeg 源码分析 - avcodec_send_packet 和 avcodec_receive_frame
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2024-10-06 01:41:59   当前IP: 3.138.122.11   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我