设为首页 加入收藏

TOP

HDU 4283 You Are the One(区间dp)
2015-11-21 00:56:53 来源: 作者: 【大 中 小】 浏览:2次
Tags：HDU 4283 You Are the One 区间
??

题意：有n个人排成一排要上台表演，每个人有一个?丝值pi。第i个上台表演的人，他的不满意度为(i-1)*pi。

现在有一个类似于栈的黑屋子，你可以让某些人进入这个黑屋子。这些人要按照排的顺序来，那么对于排在最前面的人，

就有两个选择：

（1）让他直接上台表演；

（2）让他暂时进黑屋子。

现在请你选择一个合理的调度顺序，使得最后的总不满意度最小？

训练的时候想的是贪心，将后来想了想这样并不对，看了题解才知道可以用区间dp来做，还是姿势水平不够。

思路：区间dp，对于一个区间[i, j]，区间第一个元素i可能在任意时刻上台，假设他第k个上台，那么不管怎样

区间[i+1, i+k-1]这k-1个元素一定在i之前上台，

区间[i+k, j]一定在i之后上台。

那么我们就可以得到状态转移方程

dp(L, R) = min(dp(L+1, i)+(i-L)*ds[L]+dp(i+1, R)+(su[R]-su[i])*(i+1-L))

?

#include
  
     
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
          #include
          
            #include
           
             #include
            
              #include
              #include
              
                #define eps 1e-6 #define LL long long using namespace std; //const int maxn = 100 + 5; const int INF = 0x3f3f3f3f; int n; int d[105][105], su[105]; int ds[105]; int dp(int L, int R) { if(L >= R) return 0; if(d[L][R] != -1) return d[L][R]; d[L][R] = INF; for(int i = L; i <= R; i++) { d[L][R] = min(d[L][R], dp(L+1, i)+(i-L)*ds[L]+dp(i+1, R)+(su[R]-su[i])*(i+1-L)); } return d[L][R]; } int kase; int main() { // freopen(input.txt, r, stdin); int t; cin >> t; while(t--) { memset(d, -1, sizeof(d)); scanf(%d, &n); for(int i = 1; i <= n; i++) { scanf(%d, &ds[i]); su[i] = su[i-1] + ds[i]; } printf(Case #%d: %d , ++kase, dp(1, n)); } return 0; }

?

?
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：POJ 2417/BZOJ 3239(Discrete Log.. 下一篇：HDOJ 题目4276 The Ghost Blows L..

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: