您当前位置：首页 > php开源 > 综合技术 > 【HDU 4283】You Are the One（区间DP）

【HDU 4283】You Are the One（区间DP）

来源：程序员人生发布时间：2016-12-12 15:22:58 阅读次数：2262次

【HDU 4283】You Are the One（区间DP）

读错了发题意……

原意是n个人的队列，不断出队，每次可以直接拿走，或暂存在1个临时栈里。

离开1个人需要1s，每一个人的愤怒值与它的等待时间（在它前离开的人的数量k)成正比，为val[i]*k，val[i]为第i个人的愤怒比率

问怎样奇妙的应用这个栈，让总的愤怒值最少。

万万没想到是区间DP……

对这类队列和栈互弄的可以找到1个规则：
第i个人出栈（离开）后，之前在栈中的，只能按编号从小到大的顺序离开

那末斟酌dp[i][j]表示区间[i,j]的人都离开的最少花费。

转移的时候，斟酌在这个区间中，第i个人是第k个离开的，k只是相对[i,j]这个区间的编号，即取值为 k∈[0,j−i]

那末对每一个k，第i个人第k个走，0→k−1走的只能是i+1→i+k
那末[i,k]的花费为dp[i+1][i+k]+val[i]∗k

[k+1,j]相对于[i,k]的花费实际上是dp[k+1][j]+(k+1)∗∑r=k+1jval[r]

这样转移方程就出来了：
dp[i][j]=minj−ik=0(dp[i][j],dp[i+1][i+k]+val[i]∗k+dp[k+1][j]+(k+1)∗∑r=k+1jval[r])

代码以下：

#include <iostream>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <climits>
#include <ctime>
#include <cstring>
#include <queue>
#include <stack>
#include <list>
#include <algorithm>
#include <map>
#include <set>
#define LL long long
#define Pr pair<int,int>
#define fread(ch) freopen(ch,"r",stdin)
#define fwrite(ch) freopen(ch,"w",stdout)

using namespace std;
const int INF = 0x3f3f3f3f;
const int msz = 10000;
const int mod = 1e9+7;
const double eps = 1e⑻;

int n;
int val[233];
int sum[233][233];
int dp[233][233];

int main()
{
    //fread("");
    //fwrite("");

    int t;

    scanf("%d",&t);

    for(int z = 1; z <= t; ++z)
    {
        scanf("%d",&n);

        for(int i = 0; i < n; ++i) scanf("%d",&val[i]);

        for(int i = 0; i < n; ++i)
            for(int j = i; j < n; ++j)
            {
                if(i == j) sum[i][j] = val[i];
                else sum[i][j] = sum[i][j-1]+val[j];
            }

        memset(dp,INF,sizeof(dp));
        for(int len = 1; len <= n; ++len)
        {
            for(int i = 0,j = i+len-1; j < n; ++i,++j)
            {
                for(int k = 0; k < len; ++k)
                {
                    dp[i][j] = min(dp[i][j],(i+1 <= i+k? dp[i+1][i+k]: 0)+val[i]*k+(i+k+1 <= j? (dp[i+k+1][j]+sum[i+k+1][j]*(k+1)): 0));
                }
            }
        }

        printf("Case #%d: %d\n",z,dp[0][n-1]);
    }

    return 0;
}

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

------分隔线----------------------------

上一篇 Leetcode 59 Spiral Matrix II

下一篇 数据结构学习笔记（一）：基本概念：什么是数据结构和算法，应用实例

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点