首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。