HDU1565 方格取数 &&uva 11270 轮廓线DP

方格取数(1)

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 8851 Accepted Submission(s): 3386

Problem Description

给你一个n*n的格子的棋盘，每个格子里面有一个非负数。
从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取的数所在的2个格子不能相邻，并且取出的数的和最大。

Input

包括多个测试实例，每个测试实例包括一个整数n 和n*n个非负数(n<=20)

Output

对于每个测试实例，输出可能取得的最大的和

Sample Input

Sample Output

188

Author

ailyanlu

Source

Happy 2007

Recommend

前面的骨牌堆放由于数据不是很大用暴力状压就过去了这个题目如果还是O(2^n*2^n*m)

得话复杂度显然爆炸，所以采用轮廓线dp的思想，O(n*m*2^(n))

对于每个格子影响他的只有四周相邻的格子，我们从左至右，由上而下递推得话，对于正在处理的格子，影响他的最多只有左边相邻和上方相邻的格子，

我们不妨以n为轮廓线长度，对于每个格子有两种操作，取or不取，不取得话可由任意状态得到，取得话只要左方&&上方状态为0表示不取即可

对于当前处理的格子我们枚举上个轮廓线的状态看是否能转移到当前轮廓线，如果可以，update即可。

最后遍历一遍得到答案。

之所以复杂度变低是采取了我为人人的方法，少遍历一遍2^n，很巧妙的思想，我会把骨牌堆放以这种方法再做一次。

#include<bits/stdc++.h>
using namespace std;
int ans;
int dp[2][(1<<20)+5];
bool judge(int a,int b){return (a&(1<<b));}
int clr(int a,int b){ if(judge(a,b)){return (a^(1<<b));}
else return a;}
void update(int cur,int now,int pre,int num)
{
    dp[cur][now]=max(dp[cur][now],dp[1-cur][pre]+num);      //我为人人
}
int main()
{
    int e[25][25],i,j,k,s,t,n;
    while(cin>>n){int cur=0;
        for(i=0;i<n;++i)
            for(j=0;j<n;++j)
                   cin>>e[i][j];
        memset(dp,0,sizeof(dp));
        for(i=0;i<n;++i){
            for(j=0;j<n;++j){
                cur^=1;memset(dp[cur],0,sizeof(dp[cur]));
                for(k=0;k<(1<<n);++k){
                    update(cur,clr(k<<1,n),k,0);
                   if(!j){
                       if(!judge(k,n-1)){
                    update(cur,clr((k<<1)+1,n),k,e[i][j]);
                       }
                   }
                   else{
                    if((!judge(k,0))&&(!judge(k,n-1))){
                         update(cur,clr((k<<1)+1,n),k,e[i][j]);
                    }
                   }
                }
            }
        }
     ans=0;
    for(i=0;i<(1<<n);++i) ans=max(ans,dp[cur][i]);
    cout<<ans<<endl;
    }
    return 0;
}

Given a rectangular grid, with dimensions

, compute the number of ways of completely tiling it

with dominoes. Note that if the rotation of one tiling matches another, they still count as different

ones. A domino is a shape formed by the union of two unit squares meeting edge-to-edge. Equivalently,

it is a matching in the grid graph formed by placing a vertex at the center of each square of the region

and connecting two vertices when they correspond to adjacent squares. An example of a tiling is shown

below.

Input

The input will consist of a set of lines with

, given the restriction

101.

Output

For each line of input, output the number of tilings in a separate line.

Sample Input

2 10

4 10

8 8

Sample Output

89

18061

12988816

题目不再赘述就是骨牌放置问题，这里采用轮廓线dp
要注意的就是横放时列数不能为1，竖放时行不能为1，md最近一直犯zz错误，cout ans数组我一直cout dp数组检查半天mb

#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL dp[2][(1<<11)];
LL ans[101][101];
bool judge(int a,int b){return (a&(1<<b));}
int clr(int a,int b){return (a>>b)?(a^(1<<b)):a;}
void update(int cur,int now,int pre) { dp[cur][now]+=dp[1-cur][pre]; }
int main()
{
    int i,j,k,n,m,s,t;
    memset(ans,-1,sizeof(ans));
    while(cin>>n>>m){int cur=0;
    memset(dp,0,sizeof(dp));
        if(n*m%2==1) {puts("0");continue;}
        if(ans[n][m]+1) {cout<<ans[n][m]<<endl;continue;}
        if(m>n) swap(m,n);
        dp[cur][(1<<m)-1]=1;
        for(i=1;i<=n;++i){
            for(j=1;j<=m;++j){cur^=1;memset(dp[cur],0,sizeof(dp[cur]));
                for(k=0;k<(1<<m);++k){
                  if(judge(k,m-1)) update(cur,clr((k<<1),m),k);  //不放
                  if(i>1&&!judge(k,m-1)) update(cur,(k<<1)^1,k);      //竖放
                  if(j>1&&(!judge(k,0))&&judge(k,m-1)) update(cur,clr((k<<1)^3,m),k);   //横放
                }
            }
        }
        ans[n][m]=ans[m][n]=dp[cur][(1<<m)-1];
        cout<<ans[n][m]<<endl;
    }
    return 0;
}