注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zorksylar

Nothing is impossible , if distributed.

 
 
 

日志

 
 

【动态规划】rqnoj5 能量项链  

2011-09-20 15:54:47|  分类: ACM_动态规划 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题目链接:
题目描述:
在Mars星球上,每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子,这些标记对应着某个正整数。并且,对于相邻的两颗珠子,前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样,通过吸盘(吸盘是Mars人吸收能量的一种器官)的作用,这两颗珠子才能聚合成一颗珠子,同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m,尾标记为r,后一颗能量珠的头标记为r,尾标记为n,则聚合后释放的能量为m*r*n(Mars单位),新产生的珠子的头标记为m,尾标记为n。
需要时,Mars人就用吸盘夹住相邻的两颗珠子,通过聚合得到能量,直到项链上只剩下一颗珠子为止。显然,不同的聚合顺序得到的总能量是不同的,请你设计一个聚合顺序,使一串项链释放出的总能量最大。
例如:设N=4,4颗珠子的头标记与尾标记依次为(2,3) (3,5) (5,10) (10,2)。我们用记号?表示两颗珠子的聚合操作,(j?k)表示第j,k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为:
(4?1)=10*2*3=60。
这一串项链可以得到最优值的一个聚合顺序所释放的总能量为
((4?1)?2)?3)=10*2*3+10*3*5+10*5*10=710。

输入格式

输入文件的第一行是一个正整数N(4≤N≤100),表示项链上珠子的个数。第二行是N个用空格隔开的正整数,所有的数均不超过1000。第i个数为第i颗珠子的头标记(1≤i≤N),当1≤i<N时,第i颗珠子的尾标记应该等于第i+1颗珠子的头标记。第N颗珠子的尾标记应该等于第1颗珠子的头标记。
至于珠子的顺序,你可以这样确定:将项链放到桌面上,不要出现交叉,随意指定第一颗珠子,然后按顺时针方向确定其他珠子的顺序。

输出格式

  输出文件只有一行,是一个正整数E(E≤2.1*10^9),为一个最优聚合顺序所释放的总能量。

样例输入

4 2 3 5 10

样例输出

710

分析:
经典的石子合并问题,记忆化搜索,dp[x][y] 表示项链的x到y合并后的最大能量,记忆化搜,注意题目中是有环的

#include <cstdio>
#include <algorithm>
#include <cstring>

#define MAXN 110                
using namespace std;

int n;
struct Node
{
        int head;
        int rear;
};

Node data[MAXN];


long long dp[MAXN][MAXN];
bool visit[MAXN][MAXN];

void init()
{
        int i;
        int temp[MAXN];
        memset(dp,0,sizeof(dp));
        memset(visit,0,sizeof(visit));
        for(i = 0;i < n;i ++)
                scanf("%d",&temp[i]);
        for(i = 0;i < n;i ++)
        {
                data[i].head = temp[i%n];
                data[i].rear = temp[(i+1)%n];
        }
}

long long max(long long a,long long b)
{
        return a > b ? a : b;
}

int dfs(int x,int y)
{
        
        int k;
        if(visit[x][y]) return dp[x][y];
        if(x > y)
        {
                for(k = x;k < n+y;k ++)
                {
                        dp[x][y] = max(dp[x][y],
                                   dfs(x,k%n) + dfs((k+1)%n,y) +
                                   data[x].head* data[(k+1)%n].head * data[y].rear);
                }
                visit[x][y] = true;
                return dp[x][y];
        }
        else if(x < y)
        {
                for(k = x;k < y;k ++)
                {
                        dp[x][y] = max(dp[x][y],
                                   dfs(x,k) + dfs(k+1,y) + 
                                   data[x].head * data[k+1].head * data[y].rear);
                }
                visit[x][y] = true;
                return dp[x][y];
        }
}

void work()
{
        long long ans = 0;
        int i;
        for(i = 0;i < n;i ++)
        {
                dp[i][i] = 0;
                visit[i][i] = true;
        }
        for(i = 0;i <= n-1;i ++) //对环的处理,比较笨
        {
                dfs(i,(i+n-1) % n);
                ans = max(ans,dp[i][(i+n-1) % n]);
        }
        printf("%lld\n",ans);
}

int main()
{
        scanf("%d",&n);
        init();
        work();
        return 0;
}

  评论这张
 
阅读(157)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018