【HDU 4283】You Are the One（區間DP）
讀錯了發題意……
原意是n個人的隊列，不斷出隊，每次可以直接拿走，或暫存在1個臨時棧里。
離開1個人需要1s，每一個人的憤怒值與它的等待時間（在它前離開的人的數量k)成正比，為val[i]*k，val[i]為第i個人的憤怒比率
問怎樣奇妙的應用這個棧，讓總的憤怒值最少。
萬萬沒想到是區間DP……
對這類隊列和棧互弄的可以找到1個規則：
第i個人出棧（離開）后，之前在棧中的，只能按編號從小到大的順序離開
那末斟酌
轉移的時候，斟酌在這個區間中，第i個人是第k個離開的，k只是相對
那末對每一個k，第i個人第k個走，
那末
這樣轉移方程就出來了：
代碼以下：
#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;
}
程序員人生，我編程，我富裕，記住wfuyu網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
