题目描述

求在一个区间上的某种性质。枚举所有可能的窗口大小，如果可以滑动，从左到右滑动一次。

细节见注释

#include<iostream>
using namespace std;

#define ffor(i,s,e) for(int i=s;i<e;i++)
const int N=302;
const int INF=1e9;

int f[N][N];
int s[N];//前缀和

int main(){
    int n;cin>>n>>s[0];
    ffor(i,1,n) {
        scanf("%d",&s[i]);
        s[i]+=s[i-1];
    }

    ffor(size,2,n+1){//枚举滑动窗口大小
        int maxl=n-size+1;
        ffor(l,0,maxl){//控制滑动起点
            int r=l+size-1;
            f[l][r]=INF;
            ffor(k,l,r+1){//枚举所有可能的分割点
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
            }
        }
    }

    cout<<f[0][n-1]<<endl;
    return 0;
}