首页 > 代码库 > UVALive 6560 The Urge to Merge

UVALive 6560 The Urge to Merge

题目链接:传送门

题目大意:有一个 3*n 的矩阵,每个格子里有一个数,你可以选择相邻的两个格子合并成一个,并且权值变为两数乘积,若一个数未合并,权值变为0,求最后权值总和最大值。

题目思路:以 2^3 状态压缩。

#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <cstring>#include <stack>#include <cctype> #include <queue>#include <string>#include <vector>#include <set>#include <map>#include <climits>#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,r#define fi first#define se second#define ping(x,y) ((x-y)*(x-y))#define mst(x,y) memset(x,y,sizeof(x))#define mcp(x,y) memcpy(x,y,sizeof(y))using namespace std;#define gamma 0.5772156649015328606065120#define MOD 1000000007#define inf 0x3f3f3f3f#define N 2000005#define maxn 100005typedef pair<int,int> PII;typedef long long LL;int n,m,cnt,ans;int a[1005][5];int dp[1005][10];int deal(int x,int u,int e){    for(int i=0;i<3;++i)if((u&(1<<i))&&(e&(1<<i)))return 0;    int temp=0;    for(int i=0;i<3;++i){        if(e&(1<<i)){            temp+=a[x-1][i+1]*a[x][i+1];        }    }    int t1=0,t2=0;    e|=u;    if((!(e&1))&&(!(e&2)))t1=a[x][1]*a[x][2];    if((!(e&2))&&(!(e&4)))t2=a[x][2]*a[x][3];    temp+=max(t1,t2);    return temp;}int main(){    int i,j,Case=0;    while(scanf("%d",&n)!=EOF&&n){        mst(dp,0);        for(i=1;i<=3;++i)for(j=1;j<=n;++j)scanf("%d",&a[j][i]);        for(i=1;i<=n;++i){            for(j=0;j<=8;++j)            for(int k=0;k<=8;++k){                int temp=deal(i,j,k);                dp[i][j]=max(dp[i][j],dp[i-1][k]+temp);            }        }        ans=0;        for(i=0;i<=8;++i) ans=max(ans,dp[n][i]);        printf("Case %d: %d\n",++Case,ans);    }    return 0;}

 

UVALive 6560 The Urge to Merge