[Acwing] 1068. 环形石子合并 区间DP

前言

传送门 : https://www.acwing.com/problem/content/1070/ 没想到感冒一会,就两天没做题了,真恐怖QAQ

思路

朴素做法 : 对于n个点,我们需要合并n-1次,因此我们有n种方法进行合并,但是如果都枚举出来这n种 时间复杂度是 O ( n 4 ) O{(n^4)} O(n4) 会TLE

因此我们可以开 两倍数组 进行优化

CODE

#include 
using namespace std;
const int N  = 410 ,INF =0x3f3f3f3f;

int n;
int w[N],s[N];
int f[N][N],g[N][N];
void solve()
{
    cin>>n;
    for(int i=1;i>w[i];
        w[i+n] = w[i];///两倍数组
    }

    for(int i=1;i