区间dp-zoj3541-The Last Puzzle - c++编程基础

TOP

区间dp-zoj3541-The Last Puzzle

2014-11-23 21:46:36 来源: 作者: 【大中小】浏览:7次

Tags：区间 dp-zoj3541-The Last Puzzle

题目大意：

在数轴上，有n个按钮，位置递增为d1,d2,..dn，每个按钮对应一个时间为t1,t2,...tn.每次每个按钮按下后，t1秒后会自动弹起来。每走单位距离花费单位时间，问以怎样的顺序按，能够保证所有的按钮都能够被按下去。

解题思路：

区间dp.

这题hdu 4053提交过不了，spj可能有问题。

对于某一区间A~B的按钮，一定是先按某个端点，如果不是,假设先按中间的K，然后肯定要按一个端点，再之后会按另外一个端点，中间肯定会经过K点，所以先按k不如后按k。

dp[i][j][0]表示在区间i~j内先按左边端点能达到的最小的时间，dp[i][j][1]表示先按右端点能达到的最小时间。

dp[i][j][0]=Min(dp[i+1][j][0]+dp[i+1]-dp[i],dp[i+1][j]+dp[j][-dp[i]);

path[i][j][]表示对应状态表示的端点（左还是右）。

代码：


 
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#define eps 1e-6  
#define INF 0x3fffffff  
#define PI acos(-1.0)  
#define ll __int64  
#define lson l,m,(rt<<1)  
#define rson m+1,r,(rt<<1)|1  
#pragma comment(linker, "/STACK:1024000000,1024000000")  
using namespace std;  
  
  
//freopen("data.in","r",stdin);  
//freopen("data.out","w",stdout);  
  
#define Maxn 220  
  
ll dp[Maxn][Maxn][2];  
int pa[Maxn][Maxn][2];  
//dp[i][j][0]表示区间i~j从左边端点开始按 dp[][][1]表示从右边端点开始  
//path[i][j][k]表示与之对应的状态。  
int ti[Maxn],di[Maxn];  
int n;  
  
int main()  
{  
   while(scanf("%d",&n)!=EOF)  
   {  
      for(int i=1;i<=n;i++)  
         scanf("%d",&ti[i]);  
      for(int i=1;i<=n;i++)  
         scanf("%d",&di[i]);  
      memset(dp,0,sizeof(dp)); //时间为0  
      for(int gap=2;gap<=n;gap++)  
      {  
         for(int i=1;i+gap-1<=n;i++)  
         {  
            int j=i+gap-1;  
  
            if(dp[i+1][j][0]+di[i+1]-di[i]=INF)  
               dp[i][j][0]=INF;  
  
            if(dp[i][j-1][1]+di[j]-di[j-1]<=dp[i][j-1][0]+di[j]-di[i])  
            {  
               dp[i][j][1]=dp[i][j-1][1]+di[j]-di[j-1];  
               pa[i][j][1]=1; //从右边  
            }  
            else  
            {  
               dp[i][j][1]=dp[i][j-1][0]+di[j]-di[i];  
               pa[i][j][1]=0;//从左边  
            }  
            if(ti[j]<=dp[i][j][1]||dp[i][j][1]>=INF)  
               dp[i][j][1]=INF; //置为无效状态  
         }  
      }  
      int l,r,va;  
      if(dp[1][n][0]


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：HDU3208(区间指数和)	下一篇：France '98

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: