| input | output |
|---|---|
7
3 4 2 2 1 4 1
|
9
|
题意：
有n个阳台围成一个环，编号为1~n，每一个阳台上有一个敌人，每一个敌人有一个伤害值。
你有一把枪，这把枪的功能是：
每次你射编号为j的阳台，j相邻的2个阳台也同时会被射中。
但是，每次你开一枪后，剩下的敌人都会给你一次伤害。
问：在你消灭所有敌人的时候，你受到的最小伤害是多少。
由n的范围，明显是状态压缩了。
二进制表示时，1表示这个敌人还没有被杀，0表示这个敌人被杀了。
dp[i]表示还剩下i的二进制的敌人时，受到的最小伤害。
则：初始化：dp[(1<<n)-1]
目标：dp[0]
sum[i]表示还剩下i的二进制表示的敌人时，能够给人造成的伤害。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 5 using namespace std; 6 7 const int inf=0x3f3f3f3f; 8 const int maxn=22; 9 10 int dp[1<<maxn]; 11 int sum[1<<maxn]; 12 int w[maxn]; 13 14 int main() 15 { 16 int n; 17 while(scanf("%d",&n)!=EOF) 18 { 19 for(int i=0;i<n;i++) 20 scanf("%d",&w[i]); 21 for(int i=0;i<(1<<n);i++) 22 dp[i]=inf; 23 dp[(1<<n)-1]=0; 24 25 memset(sum,0,sizeof(sum)); 26 for(int i=0;i<=(1<<n);i++) 27 { 28 for(int j=0;j<n;j++) 29 if(i&(1<<j)) 30 sum[i]+=w[j]; 31 } 32 33 for(int i=(1<<n)-1;i>=0;--i) 34 { 35 for(int j=0;j<n;j++) 36 { 37 if(!(i&(1<<j))) 38 continue; 39 int x=i-(1<<j); 40 int t1=j-1; 41 if(t1<0) 42 t1=n-1; 43 int t2=j+1; 44 if(t2>=n) 45 t2=0; 46 if(x&(1<<t1)) 47 x-=(1<<t1); 48 if(x&(1<<t2)) 49 x-=(1<<t2); 50 dp[x]=min(dp[x],dp[i]+sum[x]); 51 } 52 } 53 printf("%d\n",dp[0]); 54 } 55 return 0; 56 }
URAL 1152 Faise Mirrors 状压DP 简单题
原文：http://www.cnblogs.com/-maybe/p/4548095.html
