那环型DP怎么做？

常规
1

2. 石子合并2

XJOI - 题目ID：15699必做题100分

最新提交：0 分

历史最高：0 分

时间限制: 1000ms

空间限制: 524288kB

题目描述

有N堆石子排成一圈,其中第i堆的石子的重量为A_iAi​，现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆合并成新的一堆，形成的新石子堆的重量以及消耗的体力都是两堆石子的重量之和。求把全部N堆石子合并成一堆最少需要消耗多少体力。

输入格式

第一行一个正整数N（N<=300），表示石子的堆数N。第二行N个正整数，表示每堆石子的质量(<=1000)。

输出格式

一个正整数，表示最少需要消耗多少体力。

样例

Input 1

4 1 3 5 2

Output 1

20

样例解释

合并1、2堆，再合并3，4堆

数据范围

N<=300, 石子的质量<=1000

切记：不要发代码！！！！！！！！！

1 个赞
2

5 个帖子被合并到现有话题中：垃圾站/废贴集中

3

我只会半题

1 个赞
4

不好意思发错了
正文：

image
image2978×1431 101 KB

1 个赞
5

破环成链即可
不过，要注意i的范围

警示后人！

6

我的帖为啥被移动了

7 
#include <bits/stdc++.h>
using namespace std;

int a[666]; 

int dp[610][610];

int sum[610];

int n; 

int main(){
	
	cin >> n;
	
	for (int i = 1;i <= n;i++){
		cin >> a[i];
		a[n+i] = a[i];
	}
	
	for (int i = 1;i <= n;i++){
		sum[i] = sum[i-1] + a[i];
	}
	
	for (int len=2;len<=n;len++)
	{
		for (int l = 1,r = len + l -1;r <= n;l++,r++)
		{
            dp[l][r]=INT_MAX;
			for (int k = l;k < r;k++)
			{
				dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]);
			}
		}
	}
	
	int maxn = INT_MAX;
	
	for (int i = 1;i <= 2*n;i++){
		cout << dp[1][n]<<endl;
	}
	
	
	return 0;
}

样例过不了

8

你写的方法不对