P1880 [NOI1995] 石子合并【模板】区间DP
~~~~~ P1880 [NOI1995] 石子合并 ~~~~~ 总题单链接
思路
~~~~~ 任何一个区间最后都会合并为两个区间，然后再把这两个区间合并。
~~~~~ 对于每一个区间，枚举最后剩下的两个区间即可转移。
~~~~~ 具体操作时（求最小）：设 d p [ i ] l e n ] dp[i]len] dp[i]len] 表示以 i i i 为左端点，长度为 l e n len len 的区间合并为一堆石子的最小代价。
~~~~~ d p [ i ] [ l e n ] = m i n ( d p [ i ] [ j − i + 1 ] , d p [ j + 1 ] [ i + l e n − j − 1 ] ) , i ≤ j < i + l e n − 1 dp[i][len]=min(dp[i][j-i+1],dp[j+1][i+len-j-1]),i\leq j< i+len-1 dp[i][len]=min(dp[i][j−i+1],dp[j+1][i+len−j−1]),i≤j<i+len−1。
~~~~~ 求最大同理。
代码
#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f3f3f3f
using namespace std;ll n,ans,a[205],pre[205],dp[205][205];signed main(){ios::sync_with_stdio(false);cin>>n;for(ll i=1;i<=n;i++)cin>>a[i],a[i+n]=a[i];for(ll i=1;i<=n*2;i++)pre[i]=pre[i-1]+a[i];// 求最小 memset(dp,0x3f,sizeof(dp));for(ll i=1;i<=n*2;i++)dp[i][1]=0;for(ll len=2;len<=n;len++)for(ll i=1;i+len-1<=n*2;i++){for(ll j=i;j<i+len-1;j++)dp[i][len]=min(dp[i][len],dp[i][j-i+1]+dp[j+1][i+len-j-1]);dp[i][len]+=pre[i+len-1]-pre[i-1];}ans=INF;for(ll i=1;i<=n;i++)ans=min(ans,dp[i][n]);cout<<ans<<endl;//求最大，其实就是把 min 换成 max，以及把初始化改一下 memset(dp,-0x3f,sizeof(dp));for(ll i=1;i<=n*2;i++)dp[i][1]=0;for(ll len=2;len<=n;len++)for(ll i=1;i+len-1<=n*2;i++){for(ll j=i;j<i+len-1;j++)dp[i][len]=max(dp[i][len],dp[i][j-i+1]+dp[j+1][i+len-j-1]);dp[i][len]+=pre[i+len-1]-pre[i-1];}ans=-INF;for(ll i=1;i<=n;i++)ans=max(ans,dp[i][n]);cout<<ans;return 0;
}