湘潭网站建设湘潭振企专业,北京网站制作方案公司,新专业建设的重点任务,昆明网站建设推广公司哪家好2012天津区域赛的一道题目#xff0c;题目链接如下 You Are the One HDU - 4283 这道题目要说思想的话其实并不是很难#xff0c;但是我却没做出来。关键就在于读题读不懂#xff08;How Vegetable I am#xff01;#xff09;#xff0c;到最后搜了别人的题解才明白这道…2012天津区域赛的一道题目题目链接如下 You Are the One HDU - 4283 这道题目要说思想的话其实并不是很难但是我却没做出来。关键就在于读题读不懂How Vegetable I am到最后搜了别人的题解才明白这道题想要说什么
题目大意就是说给定一个有序序列和一个栈对于队伍前头的一个人有两个操作一个是直接迈向舞台另一个操作就是迈入栈中。在一个时间下迈向舞台的人可以是原始队伍里的人也可以是栈里面的人。举例来说假定队伍此时为 队首4 5队尾栈此时为 栈顶3 2 1 栈底,那么下一个时刻可能是4进入栈中或者4进入舞台或者3从栈中去向舞台。
我们考虑如下事实
考虑区间[l,r]区间长度k r-l1。
如果区间的第一个元素可能是第1 一直到第 k个进入舞台的假设第一个元素是第p个进入舞台的 1pk那么我们知道第一个元素一定要先入栈区间[l1,lk-1]中的元素一定会先第一个元素而进入舞台这样的话就转化到了子结构dp[l1][lk-1]中去了。
同时[lk,r]中的元素一定后于第一个元素而进入舞台。他们共同要等待的耗费为p*sum[lk,r]另外还有一部分耗费为dp[lk][r]
综上所述得到转移方程
dp[l][r] min(dp[l][r],dp[l1][lk-1] (k-1)*a[lp-1] p*sum[lk,r] dp[lk][r]); 注意代码中用的区间方式为左闭右开。 #include iostream
#include cstdio
#include algorithm
#include cstring
using namespace std;
const int MAX 105;
int dp[MAX][MAX];
int a[MAX];
int sum[MAX];
int n;
int main(){int T;scanf( %d,T);int cas 0;while(T--){memset(dp,0,sizeof(dp));scanf( %d,n);sum[0] 0;for(int i 0;i n;i){scanf( %d,a[i]);sum[i1] sum[i] a[i];}//左闭右开 for(int k 2;k n;k){for(int i 0;i k n;i){dp[i][ik] 1e9;for(int j i1;j i k;j){//第一个元素的顺序 dp[i][ik] min(dp[i][ik],dp[i1][j] (j-i-1)*a[i] (j-i)*(sum[ik] - sum[j]) dp[j][ik]);}}}printf(Case #%d: %d\n,cas,dp[0][n]);}return 0;
}
