动态规划??区间DP??区间DP
定义
定义：顾名思义就是在一段区间上用动态规划 其实就是两个过程
化零为整 化整为零 还是举个例子来说吧，要说不明白 就像经典的区间DP 合并石子
??链接??
思路分析：这个题简单来说就是把相邻的两堆合成一堆，这样从大的到小的方面分析，然后就是相当于一个线段一样
把他 往小的分。
而这个状态方程是 总的 = 左22一堆最小值 + 右一堆最小值 + 这一段的总和；
应为最后把这左右两堆加起来 是没有加这一大段的。
+一般 区间DP的 套路就是1，先枚举长度，在枚举左端点 ，在枚举右端点。
#include <map>#include <queue>#include <string>#include<iostream>#include<stdio.h>#include<string.h>#include <algorithm>#include <math.h>typedef long long ll;using namespace std;const int maxn=2e6+1010;#defineconst int mod=998244353;const int MOD=10007;inline int read(){ int x=0;bool t=false;char ch=getchar(); while((ch<‘0’||ch>’9′)&&ch!=’-‘)ch=getchar(); if(ch==’-‘)t=true,ch=getchar(); while(ch<=’9’&&ch>=’0’)x=x*10+ch-48,ch=getchar(); return t?-x:x;}ll n,t,m;ll a[500],sum[500],dp[500][500];int main(){ cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; sum[i]=a[i]+sum[i-1];//前缀和 } for(int len=2;len<=n;len++)//长度 { for(int i=1;i+len-1<=n;i++)//左堆 { int j=len+i-1;//右堆 dp[i][j]=1e18+7; for(int k=i;k<j;k++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]); } } cout<<dp[1][n]<<endl; return 0;}
【文章原创作者：ddos攻击防御 aqt.html欢迎留下您的宝贵建议】其实你已经错过了旅行的意义。
