区间dp,如果一个人入栈的话,那到这个人出栈的那一段上台的人肯定是原本位置和当前位置之间的那些人,所以这一个区间可以考虑为一种情况,所以就把问题弄成把一个大区间分解,找出满足题意的最小值了,于是就成为了区间dp问题了dp[l][r]表示只有这个区间的值时可以得到的最小值,考虑区间(l,r) 则一种情况是把区间继续往下分,于是dp[l,r] = min(dp[l,r], dp[l][i] + dp[i + 1, r] + (sum[r] - sum[i]) * (i - l + 1));或则把
l 到 i 的人放入栈中,由于l必须最后出栈构成当前考虑区间的最后一个,于是考虑是把 l 到 i 的人全放入栈中倒着输出,再加上剩下区间的情况,于是就可以求出anser 了,可以用递推做,也可以用记忆化搜索,个人比较喜欢记忆化,思路清晰些~~~
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<cmath>
#define INF 1e9
#define LL long long
#define PB(a) push_back(a);
#define CLR(a, b) memset(a, b, sizeof(a))
using namespace std;
const int N = 111;
int dp[N][N], sum[N], a[N];
int dfs(int l, int r)
{
int i, tmp;
if(dp[l][r] != -1) return dp[l][r];
dp[l][r] = INF;
for(i = l; i < r; i ++)
{
dp[l][r] = min(dp[l][r], dfs(l, i) + dfs(i + 1, r) + (sum[r] - sum[i]) * (i - l + 1));
}
tmp = 0;
for(i = l; i < r; i ++)
{
tmp += (r - i) * a[i];
dp[l][r] = min(dp[l][r], dfs(i + 1, r) + tmp);
}
return dp[l][r];
}
int main()
{
int n, t, i, j, cas = 1;
scanf("%d", &t);
while(t --)
{
scanf("%d", &n);
sum[0] = 0;
CLR(dp, -1);
for(i = 1; i <= n; i ++)
{
scanf("%d", &a[i]);
sum[i] = sum[i - 1] + a[i];
dp[i][i] = 0;
}
printf("Case #%d: %d\n", cas ++, dfs(1, n));
}
}
分享到:
相关推荐
杭州电子科技大学ACM Steps中Chapter One-Section One的答案集。不要直接抄哦~~ 如需题解请上我的博客~ 博客地址呈上:http://blog.csdn.net/xu_zh
You are given the value of m and (f(n,m)?n)⊕n, where ``⊕’’ denotes the bitwise XOR operation. Please write a program to find the smallest positive integer n that (f(n,m)?n)⊕n=k, or determine it ...
杭州电子科技大学ACM Steps中Chapter One-Section Two的答案集。不要直接抄哦~~ 如需题解请上我的博客~ 博客地址呈上:http://blog.csdn.net/xu_zh
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
hdu1001解题报告
HDU1059的代码
hdu 1574 passed sorce
nm are the integers. All integers will be positive and lie within the range of a 32-bit integer. Output For each problem instance, output a single line containing the corresponding LCM. All results ...
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
自己做的HDU ACM已经AC的题目
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦
ACM HDU题目分类,我自己总结的大概只有十来个吧