首页 > 代码库 > hdu1069（dp）

hdu1069（dp）

2024-08-04 01:35:02   216人阅读

 

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1069

 

分析： 每种石头有六种方法，那么等效为：有6*n种石头。

根据x和y排序（要保证相应的x、y总有x>=y），然后dp[i]=
max{s[i].z,s[i].z+dp[j]}（j<i，且石块i放于石块j上，符合题意）。

其实就是最长上升子序列的换种求法。。。

 

#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <queue>#include <cstdlib>#include <vector>#include <set>#include <map>#define LL long longusing namespace std;int dp[200];struct node{    int x,y,z;}s[200];int cmp(node a,node b){    if(a.x!=b.x)return a.x>b.x;    else if(a.y!=b.y)return a.y>b.y;    else return a.z>b.z;}int main(){    int n,cas=1;    while(scanf("%d",&n)&&n)    {        int tot=1;        for(int i=1;i<=n;i++)        {            int x,y,z;            scanf("%d%d%d",&x,&y,&z);            s[tot].x=x;s[tot].y=y;s[tot].z=z;            tot++;            s[tot].x=x;s[tot].y=z;s[tot].z=y;            tot++;            s[tot].x=y;s[tot].y=x;s[tot].z=z;            tot++;            s[tot].x=y;s[tot].y=z;s[tot].z=x;            tot++;            s[tot].x=z;s[tot].y=y;s[tot].z=x;            tot++;            s[tot].x=z;s[tot].y=x;s[tot].z=y;            tot++;        }        sort(s+1,s+tot,cmp);        memset(dp,0,sizeof(dp));        dp[1]=s[1].z;        int ans=-1;        for(int i=2;i<tot;i++)        {//printf("%d %d %d\n",s[i].x,s[i].y,s[i].z);            int mx=0;            for(int j=1;j<i;j++)                if(s[j].x>s[i].x&&s[j].y>s[i].y&&dp[j]+s[i].z>mx)mx=dp[j]+s[i].z;            if(mx==0)dp[i]=s[i].z;            else            dp[i]=mx;            ans=max(mx,ans);        }        printf("Case %d: maximum height = %d\n",cas++,ans);    }}
View Code

 

hdu1069（dp）


联系
我们