首页 > 代码库 > 炮兵阵地
炮兵阵地
poj1185:http://poj.org/problem?id=1185
题意：这道题太经典了，看到题目就知道题意，故题意略。
题解：经典的状压dp。以前觉得dp是个很难的东西，做了这一题之后发现，dp其实根本不难，真的，而且很好打。
思维过程：拿到题之后，由于之前做过，所以知道是状压dp。接着想怎么解决。普通的dp，不要考虑障碍，这一题中有障碍限制。多以第一步要处理这个障碍。想到了用这样的方式来解决。把出现h的地方标记为1，其余记0，从右到左，从低位到高位，求出这个数，然后枚举状态的时候，只要把枚举的状态，和这个数&，如果出现1则是不满足的，说明有炮兵出现在H上。好了，障碍解决了。接下来可以dp。一开始想到的是用二维的，发现打出的结果不对，检查一一下，貌似转移不太对。于是，就考虑三维的了。一下子豁然开朗，思路很清晰了。打完之后，过了样例，接着交了，结果wa。不知道错在哪里，就看了discuss。其实这是不对的，应该自己思考。其实，这时候，如果找不出来错误，应该具几组特例的。会发现 11 p，就不对，然后就知道错在哪里，一开始我是第一行初始化dp[i][0],但是最后的结果却是从1开始枚举，所以如果样例只有1,2行的话，答案就不对了。于是，改改，交了，就过了。这里还有一个问题，就是，dp[][i][j],记录的是第i个状态，不是i所代表的状态，真正的状态是s[i],这样就节省了很多空间，这样开3维的才有可能。接下来，是我的代码。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 int n,m; 7 char mp[102][12]; 8 int state[102]; 9 int ct[1003],num,s[1003];10 int dp[102][67][67];11 bool isok(int x){12 if((x&(x<<1))||(x&(x<<2)))return false;13 return true;14 }15 void solve1(){16 for(int i=1;i<=n;i++){17 int counts=1,ans=0;18 for(int j=m;j>=1;j--){19 if(mp[i][j]==‘H‘)20 ans+=counts;21 counts*=2;22 }23 state[i]=ans;24 }25 }26 int counts(int x){27 int ans=0;28 while(x){29 ans+=(x&1);30 x/=2;31 }32 return ans;33 }34 void solve2(){35 num=0;36 for(int i=0;i<(1<<m);i++){37 if(isok(i)){38 num++;39 s[num]=i;40 ct[num]=counts(i);41 }42 }43 }44 int main(){45 while(~scanf("%d%d",&n,&m)){46 memset(mp,0,sizeof(mp));47 memset(dp,0,sizeof(dp));48 memset(ct,0,sizeof(ct));49 memset(s,0,sizeof(s));50 memset(state,0,sizeof(state));51 for(int i=1;i<=n;i++)52 for(int j=1;j<=m;j++)53 cin>>mp[i][j];54 solve1();55 solve2();56 for(int i=1;i<=num;i++){57 if(s[i]&state[1])continue;58 dp[1][i][0]=ct[i];59 }60 for(int i=1;i<=num;i++){61 for(int j=1;j<=num;j++){62 if(s[i]&s[j])continue;63 if(state[2]&s[i])continue;64 if(state[1]&s[j])continue;65 dp[2][i][j]=max(dp[2][i][j],dp[1][j][0]+ct[i]);66 }67 }68 for(int i=3;i<=n;i++){69 for(int j=1;j<=num;j++){70 if(s[j]&state[i])continue;71 for(int k=1;k<=num;k++){72 if(s[k]&s[j])continue;73 if(s[k]&state[i-1])continue;74 for(int g=1;g<=num;g++){75 if(s[k]&s[g])continue;76 if(s[j]&s[g])continue;77 if(s[g]&state[i-2])continue;78 dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][g]+ct[j]);79 }80 }81 }82 }83 int ans=0;84 for(int i=1;i<=num;i++){85 for(int j=0;j<=num;j++)86 ans=max(ans,dp[n][i][j]);87 }88 printf("%d\n",ans);89 }90 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。