题意:就是求石子归并。

题解:当范围在100左右是可以之间简单的区间dp,如果范围在1000左右就要考虑用平行四边形优化。

就是多加一个p[i][j]表示在i到j内的取最优解的位置k,注意能使用平行四边形优化的条件:

1.证明w满足四边形不等式,这里w是m的附属量,形如m[i,j]=opt{m[i,k]+m[k,j]+w[i,j]},此时大多要先证明w满足条件才能进一步证明m满足条件

2.证明m满足四边形不等式

3.证明s[i,j-1]≤s[i,j]≤s[i+1,j]

。如果在10000左右时就要用GarsiaWachs算法

 

推荐一个博客http://www.cnblogs.com/jiu0821/p/4493497.html

有详细解释。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf = 0X3f3f3f3f;
long long dp[200][200] , a[200] , sum[200];
int main() {
int n;
scanf("%d" , &n);
for(int i = 1 ; i <= n ; i++) {
scanf("%lld" , &a[i]);
}
memset(dp , inf , sizeof(dp));
for(int i = 1 ; i <= n ; i++) {
dp[i][i] = 0;
}
sum[0] = 0;
for(int i = 1 ; i <= n ; i++) {
sum[i] = sum[i - 1] + a[i];
}
for(int l = 1 ; l < n ; l++) {
for(int i = 1 ; i <= n && i + l <= n ; i++) {
int j = l + i;
for(int k = i ; k < j ; k++) {
dp[i][j] = min(dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1] , dp[i][j]);
}
}
}
printf("%lld\n" , dp[1][n]);
return 0;
}
////////////
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf = 0X3f3f3f3f;
long long dp[2010][2010] , a[2010] , sum[2010] ;
int p[2010][2010];
int main() {
int n;
scanf("%d" , &n);
for(int i = 1 ; i <= n ; i++) {
scanf("%lld" , &a[i]);
}
memset(dp , inf , sizeof(dp));
for(int i = 1 ; i <= 2 * n ; i++) {
dp[i][i] = 0;
p[i][i] = i;
}
sum[0] = 0;
for(int i = n + 1 ; i <= 2 * n ; i++) {
a[i] = a[i - n];
}
for(int i = 1 ; i <= 2 * n ; i++) {
sum[i] = sum[i - 1] + a[i];
}
for(int l = 1 ; l < n ; l++) {
for(int i = 1 ; i <= 2 * n && i + l <= 2 * n ; i++) {
int j = l + i;
for(int k = p[i][j - 1] ; k <= p[i + 1][j] ; k++) {
if(dp[i][j] > dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]) {
dp[i][j] = dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1];
p[i][j] = k;
}
}
}
}
long long MIN = dp[1][n];
for(int i = 2 ; i <= n ; i++) {
MIN = min(MIN , dp[i][i + n - 1]);
}
printf("%lld\n" , MIN);
return 0;
}
////////////////
#include <iostream>
#include <cstring>
using namespace std;
#define LL long long
const int MAXN = 50005;
int n, num;
LL ans;
int dp[MAXN];
void combine(int now) {
int j;
int temp = dp[now - 1] + dp[now];
ans += (LL)temp;
for(int i = now; i < num - 1; i++) dp[i] = dp[i + 1];
num--;
for(j = now - 1; j > 0 && dp[j - 1] < temp; j--) dp[j] = dp[j - 1];
dp[j] = temp;
while(j >= 2 && dp[j - 2] <= dp[j]) {
int d = num - j;
combine(j - 1);
j = num - d;
}
}
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d", &dp[i]);
num = 1, ans = 0;
for(int i = 1; i < n; i++)
{
dp[num++] = dp[i];
while(num>=3 && dp[num-3]<=dp[num-1]) combine(num - 2);
}
while(num > 1) combine(num - 1);
printf("%lld\n", ans);
return 0;
}
05-11 13:15