-
2663 Tri Tiling (1)
-
1160 Post Office (2)
-
2033 Alphacode (2)
-
1159 Palindrome (3)
-
1050 To the Max (4)
-
2430 Lazy Cows (7)
-
2066 Minimax Triangulation (8, challenge problem)
-
1038 Bugs Integrated, Inc. (9, challenge problem)
poj2292
DP的每个状态都对应一个string类的路径
#include<cstdio> #include<cstring> #include<string> #include<iostream> using namespace std; #define inf 1000000000 int d[35][35], path[35][35], p[35], cnt[35]; string start[35][35]; char print(int i) { if (i <= 26) return i + 'a' - 1; if (i == 27) return '+'; if (i == 28) return '*'; if (i == 29) return '/'; if (i == 30) return '?'; } int gao(char ch) { if (ch >= 'a' && ch <= 'z') return ch - 'a' + 1; if (ch == '+') return 27; if (ch == '*') return 28; if (ch == '/') return 29; if (ch == '?') return 30; } char s[35]; int cal(int x, int y) { int temp = 0, i, deep = 1; for (i = x; i <= y; ++i) { temp += cnt[i] * deep; deep++; } return temp; } int min(int x, int y) { return x < y ? x : y; } int main() { int T, n, i, j, k, temp, ans; scanf("%d", &T); while (T--) { memset(path, 0, sizeof (path)); memset(cnt, 0, sizeof (cnt)); scanf("%d", &n); while (n--) { scanf("%s", s); for (i = 0; s[i]; ++i) { cnt[gao(s[i])]++; } } for (i = 0; i <= 30; ++i) { for (j = 0; j <= 30; ++j) { start[i][j].clear(); // cout<<"star"<<start[i][j]<<endl; d[i][j] = inf; } } for (i = 2; i <= 30; ++i) { j = 1; d[j][i] = cal(1, i - 1); start[1][i] = start[1][i] + print(i); for (++j; j <= min(i - 1, 11); ++j) { d[j][i] = d[j - 1][i - 1] + cnt[i - 1]; path[i][j] = i - 1; start[j][i] = start[j - 1][i - 1] + print(i); for (k = i - 2; k >= j; --k) { temp = d[j - 1][k] + cal(k, i - 1); if (temp < d[j][i] || (temp == d[j][i] && start[j - 1][k] + print(i) < start[j][i])) { d[j][i] = temp; path[i][j] = k; start[j][i] = start[j - 1][k] + print(i); } } } } ans = inf; int pp; for (i = 11; i <= 30; ++i) { temp = d[11][i] + cal(i, 30); // printf("i=%d d11i=%d temp=%d\n", i, d[11][i], temp); if (temp < ans || (temp == ans && start[11][i] < start[11][pp])) { ans = temp; pp = i; // cout<<"###"<<start[11][pp]<<endl; } } cout << start[11][pp] << endl; } return 0; }poj2430
状态DP，每次4种状态互相转移
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct NODE { int x, h; bool operator<(const NODE& t)const { return x < t.x; } }; NODE node[1010]; int tot, place[1010], map[1010]; int d[1010][1010][5]; int wide[5] = {0, 1, 1, 2, 2}; int can(int a, int b) { if (a == 1 && (b & 2)) return 0; if (a == 2 && (b & 1)) return 0; return 1; } int main() { int n, b, k, i, j, cnt, s1, s2, temp; scanf("%d%d%d", &n, &k, &b); for (i = 0; i < n; ++i) { scanf("%d%d", &node[i].h, &node[i].x); } sort(node, node + n); // for (i = 0; i < n; ++i) // printf("* %d %d\n", node[i].h, node[i].x); place[0] = node[0].x; map[0] += node[0].h; tot = 1; for (i = 1; i < n; ++i) { if (node[i].x == node[i - 1].x) { map[tot - 1] += node[i].h; } else { place[tot] = node[i].x; map[tot] += node[i].h; ++tot; } } memset(d, -1, sizeof (d)); for (s1 = 1; s1 < 4; ++s1) { if (!can(s1, map[0])) continue; d[0][1][s1] = wide[s1]; } d[0][2][4] = 2; for (i = 0; i < tot - 1; ++i) { for (j = 1; j <= k; ++j) { for (s1 = 1; s1 <= 4; ++s1) { if (d[i][j][s1] < 0) continue; for (s2 = 1; s2 <= 4; ++s2) { if (!can(s2, map[i + 1])) continue; if ((s1 == s2 || (s1 == 4 && s2 != 3))) { temp = d[i][j][s1] + (place[i + 1] - place[i]) * wide[s2]; if (d[i + 1][j][s2] == -1 || temp < d[i + 1][j][s2]) d[i + 1][j][s2] = temp; // printf("i+1=%d j=%d s2=%d temp=%d d=%d\n", i + 1, j, s2, temp, d[i + 1][j][s2]); } if (s2 == 4 && j + 2 <= k) { temp = d[i][j][s1] + 2; if (d[i + 1][j + 2][s2] == -1 || temp < d[i + 1][j + 2][s2]) d[i + 1][j + 2][s2] = temp; } if (s2 <= 3 && j + 1 <= k) { temp = d[i][j][s1] + wide[s2]; if (d[i + 1][j + 1][s2] == -1 || temp < d[i + 1][j + 1][s2]) d[i + 1][j + 1][s2] = temp; } if (s2 == 4 && s1 != 3 && j + 1 <= k) { temp = d[i][j][s1] + place[i + 1] - place[i] + 1; if (d[i + 1][j + 1][s2] == -1 || temp < d[i + 1][j + 1][s2]) d[i + 1][j + 1][s2] = temp; } } } } } int ans = 0x7fffffff; for (j = 1; j <= 4; ++j) if (d[tot - 1][k][j] > 0 && d[tot - 1][k][j] < ans) ans = d[tot - 1][k][j]; printf("%d\n", ans); return 0; }poj2066
判弦是否在形内后，直接DP
#include<stdio.h> #include<stdlib.h> int x[55], y[55], cost[55][55]; int cas, n, i, j, k, best, sum; #define maxn 1<<30 #define min(a,b) ((a)<(b)?(a):(b)) #define max(a,b) ((a)>(b)?(a):(b)) #define fuhao(a) ((a)>(0)?(1):(0)) #define w(i,j,k) ((x[j]-x[i])*(y[k]-y[i])-(y[j]-y[i])*(x[k]-x[i])) int main() { scanf("%d", &cas); while (cas--) { scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d%d", &x[i], &y[i]); if (i > 1)sum += w(0, i - 1, i); else sum = 0; cost[i][(i + 1) % n] = 0; } for (i = 2; i < n; i++) { for (j = 0; j < n; j++) { cost[j][(j + i) % n] = maxn; for (k = 1; k < i; k++) { best = w(j, (j + k) % n, (j + i) % n); if (fuhao(sum) == fuhao(best)) { // printf("sum=%d best=%d\n", sum, best); cost[j][(j + i) % n] = min(cost[j][(j + i) % n], max(max(abs(best), cost[(j + k) % n][(j + i) % n]), cost[j][(j + k) % n])); } } } } printf("%.1lf\n", (double) cost[1][0] / 2); } }poj1038
状态DP，三进制状态
#include<cstdio> #include<cstring> inline int max(int a,int b){ return a>b?a:b; } bool mat[13][155]; int d[2][60000],state[2][60000],b[13],p[13],cnt[2]; int m,n,pre,cur,ans,j; void print(int x){ printf("print 3th of %d\n",x); int i; for(i=0;i<m;++i) {printf("%d\n",x%3);x/=3;} printf("--------------\n"); } void gao(int now,int sr,int tot){ int i; if(sr>=m-1){ // printf("j=%d now=%d\n",j,now); // print(now); if(!d[cur][now]){ state[cur][cnt[cur]++]=now; } d[cur][now]=max(d[cur][now],tot); return; } gao(now,m,tot); if(sr<=m-2){ for(i=sr;i<=m-2;++i){ if(b[i]==0 && b[i+1]==0 && mat[i][j]==0 && mat[i+1][j]==0){ // printf("i=%d\n",i); mat[i][j]=mat[i+1][j]=1; gao(now+2*p[i]+2*p[i+1],sr+2,tot+1); mat[i][j]=mat[i+1][j]=0; } } } if(sr<=m-3){ for(i=sr;i<=m-3;++i){ if(b[i]<2 && b[i+1]<2 && b[i+2]<2 && mat[i][j]==0 && mat[i+1][j]==0 && mat[i+2][j]==0){ // printf("ii=%d\n",i); mat[i][j]=mat[i+1][j]=mat[i+2][j]=1; gao(now+2*p[i]+2*p[i+1]+2*p[i+2],sr+3,tot+1); mat[i][j]=mat[i+1][j]=mat[i+2][j]=0; } } } } int main(){ // freopen("test.in","r",stdin); // freopen("test.out","w",stdout); int i,now,just,k,r,c,T; p[0]=1; for(i=1;i<10;++i) p[i]=p[i-1]*3; scanf("%d",&T); while(T--){ scanf("%d%d%d",&n,&m,&k); memset(mat,0,sizeof(mat)); memset(d,0,sizeof(d)); while(k--){ scanf("%d%d",&c,&r); mat[r-1][c-1]=1; } now=0; for(i=0;i<m;++i){ now+=p[i]; if(mat[i][0]) now+=p[i]; } state[0][0]=now; cnt[0]=1; cur=0; ans=0; for(j=1;j<n;++j){ pre=cur; cur=1-pre; cnt[cur]=0; memset(d[cur],0,sizeof(d[cur])); for(i=0;i<cnt[pre];++i){ just=state[pre][i]; for(k=0;k<m;++k){ b[k]=just%3; just/=3; } now=0; for(k=0;k<m;++k){ if(mat[k][j]){ now+=2*p[k]; }else if(b[k]==2){ now+=p[k]; } } gao(now,0,d[pre][state[pre][i]]); } } for(i=0;i<cnt[cur];++i) ans=max(ans,d[cur][state[cur][i]]); printf("%d\n",ans); } return 0; }