黑書上的DP例題

pagesectionnotitlesubmit
1131.5.1例題1括號序列POJ1141
1161.5.1例題2棋盤分割POJ1191
1171.5.1例題3決斗Sicily1822
1171.5.1例題4“舞蹈家”懷特先生ACM-ICPC Live Archive
1191.5.1例題5積木游戲http://202.120.80.191/problem.php?problemid=1244
1231.5.2例題1方塊消除http://poj.org/problem?id=1390
1231.5.2例題2公路巡邏http://202.120.80.191/problem.php?problemid=1600
1251.5.2例題3并行期望值POJ1074
1311.5.2例題6不可分解的編碼http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2475
1331.5.2例題7青蛙的煩惱http://codewaysky.sinaapp.com/problem.php?id=1014
1351.5.2例題9最優排序二叉樹http://judge.noi.cn/problem?id=1059
1381.5.2例題10Bugs公司POJ1038
1391.5.2例題11迷宮統計http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=70&page=show_problem&problem=1472
1421.5.2例題12貪吃的九頭龍http://judge.noi.cn/problem?id=1043
1511.5.3問題2最長上升子序列問題http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=17&page=show_problem&problem=1475
1511.5.3問題3最優二分檢索樹http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=15&page=show_problem&problem=1245
1521.5.3問題4任務調度問題POJ1180
1211.5.11.5.8藝術館的火災http://221.192.240.23:9088/showproblem?problem_id=1366
1441.5.21.5.10快樂的蜜月http://judge.noi.cn/problem?id=1052
1451.5.21.5.12佳佳的筷子http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1212
1461.5.21.5.13偷懶的工人POJ1337
1461.5.21.5.15平板涂色POJ1691
1471.5.21.5.16道路重建POJ1947
1471.5.21.5.17圓和多邊形http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1679
1481.5.21.5.18Jimmy落地POJ1661
1481.5.21.5.19免費糖果http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1059
1571.5.31.5.22回文詞POJ1159
1571.5.31.5.24郵局POJ1160
1581.5.31.5.26奶牛轉圈POJ1946
1581.5.31.5.27元件折疊http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1180

現在開始訓練一下DP:

遞歸動機的DP：

pku 1141?Brackets Sequence

黑書上講的第一個題目,題意就給出一個括號序列，包含有"(" ")" "[" "]" 求最少添加的括號數是的最終的序列是合法的并輸出這個序列。

思路：
首先這里求解的話要使用遞歸的思路，這是動態規劃產生的第一種動機，于是我們可以寫出記憶化搜索。進行求解。

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 <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>
#include <set>
#include <functional>
#include <numeric>
#include <sstream>
#include <stack>
#include <map>
#include <queue>#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 <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>
#include <set>
#include <functional>
#include <numeric>
#include <sstream>
#include <stack>
#include <map>
#include <queue>#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?Fight Club

題意：黑書

思路：

開始吧題意理解錯了，一位如果判斷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 <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>
#include <set>
#include <functional>
#include <numeric>
#include <sstream>
#include <stack>
#include <map>
#include <queue>#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?A Captivating Match

題意：

這題和上題目意思一樣，只不過這里是序列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 <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>
#include <set>
#include <functional>
#include <numeric>
#include <sstream>
#include <stack>
#include <map>
#include <queue>#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;
}

?

pku 1390?Blocks

題意：看給書吧..

思路：

我們考慮的是最后一段是單獨消去還是和前邊的一起消去，這樣就可以構造出遞歸的遞推式了。

題目的方塊可以表示稱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 <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>
#include <set>
#include <functional>
#include <numeric>
#include <sstream>
#include <stack>
#include <map>
#include <queue>
#include <utility>#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:

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=32

題意：黑書。。

思路：
這里每一步要么走左腿，要么走右腿，要么原地不動。DFS求解肯定超時，因為狀態數太多，所以我們只好利用DP記錄所有狀態，然后通過每一步的決策。求解所有滿足條件的狀態。

View Code 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>
#include <set>
#include <functional>
#include <numeric>
#include <sstream>
#include <stack>
#include <map>
#include <queue>#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 <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>
#include <set>
#include <functional>
#include <numeric>
#include <sstream>
#include <stack>
#include <map>
#include <queue>
#include <utility>#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 <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>
#include <set>
#include <functional>
#include <numeric>
#include <sstream>
#include <stack>
#include <map>
#include <queue>#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?A Lazy Worker

題意：

一個懶工人，他想工作的時間盡量少。有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 <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>
#include <set>
#include <functional>
#include <numeric>
#include <sstream>
#include <stack>
#include <map>
#include <queue>
#include <list>#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 117
using namespace std;const ll mod = 1000000007;
const int inf = 0x3fffffff;struct node
{int ti,ai,di;
}nd[N];int dp[260];
vector<int> 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

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/274289.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/274289.shtml
英文地址，請注明出處：http://en.pswp.cn/news/274289.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

靜態創意和動態創意_我在22歲時學到的關于創意指導的知識

靜態創意和動態創意_我在22歲時學到的關于創意指導的知識

靜態創意和動態創意During my last semester at college, I took a course titled “Collaborative Workshop”. The entire course focused on how to best collaborate within a team setting. We were placed into groups of 4 or 5. These were our “creative director” …
閱讀更多...
vim7.1在windows下的編碼設置[轉]

vim7.1在windows下的編碼設置[轉]

在gvm配置文件中&#xff1a; &#xff08;gvim安裝目錄下的_vimrc文件中&#xff09; """""""""""""""""""""""""""""&…
閱讀更多...
絕對編碼和增量編碼_用戶體驗設計師應該學習編碼嗎？ 絕對

絕對編碼和增量編碼_用戶體驗設計師應該學習編碼嗎？ 絕對

絕對編碼和增量編碼Even though I was trained as a graphic designer, I’ve never limited myself to that field exclusively. My particular interest in how things work didn’t allow me to stand still and as a young kid, I was already pulling apart all my toys t…
閱讀更多...
兩個ID

兩個ID

在itpub上注冊了ID googlgoracle &#xff0c;發過不少的求助帖子。 http://www.itpub.net/home.php?modspace&dothread&viewme 在CSDN 上ID:googlg,注冊時間挺早的2008年&#xff0c;一直也沒有弄過。 http://write.blog.csdn.net/postlist http://blog.csdn.net/goo…
閱讀更多...
完美主義怎么解決_相信我，你不要完美主義

完美主義怎么解決_相信我，你不要完美主義

完美主義怎么解決Perfectionism to UXers is like a badge of honour. We pride ourselves on the attention to detail and the drive to constantly push our work to the next level. When I asked some of my clients who share this sentiment about perfectionism, they …
閱讀更多...
MDK linker和debug的設置以及在RAM中調試

MDK linker和debug的設置以及在RAM中調試

有誤或者表述不清楚請指出&#xff0c;謝謝 硬件&#xff1a;TQ2440開發板、jlink V8 固件 軟件&#xff1a;J-LINK ARM 4.08i、MDK4.20 先解釋下MDK中三種linker之間的區別 設置集中在option linker選項卡 1.采用Target對話框中的ram和rom地址。采用此方式&#xff0c;…
閱讀更多...
FS_S5PC100 UBOOT-2011.12移植，支持DM9000

FS_S5PC100 UBOOT-2011.12移植，支持DM9000

在uboot中已經支持了DM9000驅動代碼在drivers/net/目錄下的dm9000x.c dm9000x.h 修改include/configs/smdkc100.h 文件&#xff0c;注釋掉SMC911X的支持&#xff0c;添加對DM9000的支持//#define CONFIG_SMC911X 1 /* we have a SMC9115 on-board *///#define…
閱讀更多...
為什么ui框架設計成單線程_評估UI設計的備忘單

為什么ui框架設計成單線程_評估UI設計的備忘單

為什么ui框架設計成單線程Whether you’re evaluating your design proposals or giving feedback to a colleague during a design critique or an informal conversation, you may find this actionable cheat sheet valuable. It’s quick to digest and its questions are …
閱讀更多...
css 菜單欄懸停_在CSS中構建懸停菜單

css 菜單欄懸停_在CSS中構建懸停菜單

css 菜單欄懸停A good menu design is an important part of any website or web app UI. Using only modern HTML and CSS, all kinds of menu combinations can be created to handle whatever user interactions are necessary. In this article, we’ll take a look at how…
閱讀更多...
一級學科和二級學科_在多學科團隊中工作的6個障礙（以及如何解決這些問題）

一級學科和二級學科_在多學科團隊中工作的6個障礙（以及如何解決這些問題）

一級學科和二級學科In a team with different skillsets, one can be hopeful and idealistic about the outcome. The goal is to work as one team, put users first and create awesome experiences. Unfortunately, things don’t always go as planned.在一支具有不同技能…
閱讀更多...
LBS核心技術解析（引子）

LBS核心技術解析（引子）

http://www.cnblogs.com/LBSer/archive/2013/04/25/3048754.html 引子&#xff1a; 人們常用“上知天文&#xff0c;下知地理”來形容一個人的博學&#xff0c;人們總是用三要素論“什么時間、什么地點&#xff0c;發生或干了什么事情”來描述一件事情,人們也常常借用“天時、地…
閱讀更多...
lynda ux_如何建立內部UX團隊

lynda ux_如何建立內部UX團隊

lynda uxWritten by Cassandra Naji由卡珊德拉納吉 ( Cassandra Naji)撰寫 The needs of real users are increasingly driving enterprise software design and development. Since 2013, IBM has hired close to 1500 designers and UXers, establishing the largest design…
閱讀更多...
IE6下div寬高設置

IE6下div寬高設置

IE6下寬高設置。IE下div 中沒有內容時&#xff0c;設置寬高不起作用&#xff0c;必須設置div背景色&#xff0c;并使用濾鏡。才能使Div填充目標區域。多用于&#xff0c;其他容器元素使用背景圖片&#xff0c;但是背景圖片的部分需要其他的事件支持。如跳轉。可以使用放置div的…
閱讀更多...
財務軟件開發_財務獨立對軟件開發人員的重要性

財務軟件開發_財務獨立對軟件開發人員的重要性

財務軟件開發If you read this post, chances that you are a software developer who is seeking financial advice for smart money-saving or investment or early retirement.如果您閱讀此文章&#xff0c;則您很可能是一名軟件開發人員&#xff0c;正在為精明的省錢或投資…
閱讀更多...
WIP模塊常用表結構

WIP模塊常用表結構

WIP模塊常用表結構表名: wip.wip_accounting_classes說明: 離散作業會計科目CLASS_CODE VARCHAR2(10) 帳目ORGANIZATION_ID NUMBER 組織代碼CLASS_TYPE NUMBER 帳目類型DESCRIPTION VARCHAR2(240) 描述…
閱讀更多...
book電子書數據庫設計_如何為殺手book的封面設計寫出完美的摘要

book電子書數據庫設計_如何為殺手book的封面設計寫出完美的摘要

book電子書數據庫設計逐步出版真正的假人 (BOOK PUBLISHING STEP BY STEP FOR REAL DUMMIES) I have spent 18 years in advertising, briefing designers and art directors on various projects — from the simplest typo-only banners to the most complex integrated camp…
閱讀更多...
5g的負面影響_設計系統的實施是否會對早期概念產生負面影響？

5g的負面影響_設計系統的實施是否會對早期概念產生負面影響？

5g的負面影響Athe financial institution where I was recently working the design system was maintained in Sketch libraries and code. A small team working across multiple brands means there is always a question for why we may or may not maintain something. We…
閱讀更多...
每日英語：Five Really Dumb Money Moves You've Got to Avoid

每日英語：Five Really Dumb Money Moves You've Got to Avoid

You know the smartest things to do with your money. But what are the worst moves? What should you avoid?Weirdly enough, they are things that a surprising number of people are still doing─even though they probably know, in their heart of hearts, how fool…
閱讀更多...
像素/厘米與像素/英寸區別_像素/體素藝術入門指南

像素/厘米與像素/英寸區別_像素/體素藝術入門指南

像素/厘米與像素/英寸區別Here’s some resources I’ve found helpful so you can start learning pixel or voxel art (as a continuation of this post on 3D resources). Feel free to mention anything I missed in the comments!這是我發現有幫助的一些資源&#xff0c;因…
閱讀更多...
暢通工程續 最短路

暢通工程續 最短路

某省自從實行了很多年的暢通工程計劃后&#xff0c;終于修建了很多路。不過路多了也不好&#xff0c;每次要從一個城鎮到另一個城鎮時&#xff0c;都有許多種道路方案可以選擇&#xff0c;而某些方案要比另一些方案行走的距離要短很多。這讓行人很困擾。現在&#xff0c;已知起…
閱讀更多...
最新文章

Copyright @ 2022~2023