首页 > 代码库 > AC日记——石子归并 51nod 1021
AC日记——石子归并 51nod 1021
石子归并
思路：
经典动态规划——归并类问题；
我们把状态划为n个，即1-n的n个长度为n个状态；
那么，每个长度为i的状态都可以由i-1个长度为i-1的状态推出；
所以，dp转移方程：
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
来，上代码：
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;int dp[105][105],sum[105],n;int main(){ scanf("%d",&n); memset(dp,127/3,sizeof(dp)); for(int i=1;i<=n;i++) { dp[i][i]=0; scanf("%d",&sum[i]); sum[i]+=sum[i-1]; } for(int len=2;len<=n;len++) { for(int i=1;i+len-1<=n;i++) { int ri=len+i-1; for(int j=i;j<ri;j++) { dp[i][ri]=min(dp[i][ri],dp[i][j]+dp[j+1][ri]+sum[ri]-sum[i-1]); } } } cout<<dp[1][n]; return 0;}
AC日记——石子归并 51nod 1021
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。