很經(jīng)典的一道狀態(tài)壓縮DP~

剛開始寫這道題目的時(shí)候分析了下，很明顯的二進(jìn)制壓縮，每行有1024中情況，但是每?jī)蓚€(gè)陣地之間至少要相隔2，最后一算只有60種形態(tài)。

感覺(jué)不是很麻煩就寫了，寫著發(fā)現(xiàn)不對(duì)勁，由于一行需要由前面兩行的狀態(tài)決定，而我開的是二維數(shù)組，怎么也不能完全的把信息轉(zhuǎn)換過(guò)來(lái)。。

一直很糾結(jié)于怎樣傳遞信息，最后很無(wú)奈的上網(wǎng)搜了下代碼，發(fā)現(xiàn)用三維的數(shù)組就可以了。。

DP[i][j][k]表示第i行當(dāng)前為第j種狀態(tài)，i-1行為第k種狀態(tài)，那么狀態(tài)轉(zhuǎn)移方程就很容易搞定了。。

DP[i][j][k]=max(DP[i][j][k],DP[i-1][k][h]),其中(st[j]&st[k])==0,(st[j]&st[h])==0,(st[k]&st[h])==0.

st[j]表示第j種狀態(tài)。

貼下代碼：（很齪的）

View Code 1 # include<stdio.h>
2 # include<string.h>
3 int n,m;
4 int s[11]={1,2,4,8,16,32,64,128,256,512,1024};
5 char map[105][12];
6 int DP[102][65][65];
7 int st[65];
8 int judge(int i)//判斷狀態(tài)i是否符合要求
9 {
10 int end,cur,ans;
11 end=-3;
12 cur=-1;
13 while(i)
14 {
15 cur++;
16 ans=i%2;
17 if(ans==1)
18 {
19 if(cur-end<3)
20 return 0;
21 end=cur;
22 }
23 i/=2;
24 }
25 return 1;
26 }
27 int cmp(int i)//求i的二進(jìn)制中有多少個(gè)1
28 {
29 int count=0;
30 while(i)
31 {
32 if(i%2) count++;
33 i/=2;
34 }
35 return count;
36 }
37 int max(int a,int b)
38 {
39 return a>b?a:b;
40 }
41 int main()
42 {
43 int i,j,k,h,i1,ans,temp;
44 k=0;
45 for(i=0;i<1024;i++)
46 {
47 if(judge(i)) st[k++]=i;
48 }
49 while(scanf("%d%d",&n,&m)!=EOF)
50 {
51 for(i=0;i<n;i++)
52 scanf("%s",map[i]);
53 memset(DP,0,sizeof(DP));
54 ans=0;
55 temp=0;
56 for(i=0;i<m;i++)
57 if(map[0][i]=='H') temp+=s[i];
58 for(i=0;i<k;i++)
59 {
60 if(st[i]>=s[m]) break;
61 /*for(j=0;j<m;j++)
62 if((st[i]&s[j]) && map[0][j]=='H') break;
63 if(j<m) continue;*/
64 if(st[i]&temp) continue;
65 for(j=0;j<k;j++)
66 {
67 if(st[j]>=s[m]) break;
68 DP[0][i][j]=cmp(st[i]);
69 }
70 ans=max(ans,DP[0][i][0]);
71 }
72 for(i=1;i<n;i++)
73 {
74 for(j=0;j<k;j++)
75 {
76 if(st[j]>=s[m]) break;
77 temp=0;
78 for(h=0;h<m;h++)
79 if((st[j]&s[h]) && map[i][h]=='H') break;
80 else if(st[j]&s[h]) temp++;
81 if(h<m) continue;
82 for(h=0;h<k;h++)
83 {
84 if(st[h]>=s[m]) break;
85 if(st[j]&st[h]) continue;
86 if(i==1) DP[1][j][h]=max(DP[1][j][h],DP[0][h][0]);
87 else
88 {
89 for(i1=0;i1<k;i1++)
90 {
91 if(st[i1]>=s[m]) break;
92 if(!(st[j]&st[i1]) && !(st[h]&st[i1])) DP[i][j][h]=max(DP[i][j][h],DP[i-1][h][i1]);
93 }
94 }
95 DP[i][j][h]+=temp;
96 ans=max(DP[i][j][h],ans);
97 }
98 }
99 }
100 printf("%d\n",ans);
101 }
102 return 0;
103 }

轉(zhuǎn)載于:https://www.cnblogs.com/183zyz/archive/2011/07/30/2122143.html

總結(jié)

以上是生活随笔為你收集整理的pku 1185 炮兵阵地的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。