您的位置:首页 > 文旅 > 旅游 > P1880 [NOI1995] 石子合并【模板】区间DP

P1880 [NOI1995] 石子合并【模板】区间DP

2024/12/23 9:13:22 来源:https://blog.csdn.net/MC_wansui/article/details/141787989  浏览:    关键词: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][ji+1],dp[j+1][i+lenj1]),ij<i+len1

~~~~~      求最大同理。

代码

#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;
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com