「JoyOI1055」沙子合并
题目描述
设有N堆沙子排成一排，其编号为1，2，3，…，N（N< =300）。每堆沙子有一定的数量，可以用一个整数来描述，现在要将这N堆沙子合并成为一堆，每次只能合并相邻的两堆，合并的代价为这两堆沙子的数量之和，合并后与这两堆沙子相邻的沙子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同，如有4堆沙子分别为 1 3 5 2 我们可以先合并1、2堆，代价为4，得到4 5 2 又合并 1，2堆，代价为9，得到9 2 ，再合并得到11，总代价为4+9+11=24，如果第二步是先合并2，3堆，则代价为7，得到4 7，最后一次合并代价为11，总代价为4+7+11=22；问题是：找出一种合理的方法，使总的代价最小。输出最小代价。
输入
第一行一个数N表示沙子的堆数N。 第二行N个数，表示每堆沙子的质量。 < =1000
输出
合并的最小代价
样例输入
4 1 3 5 2
样例输出
22
题解
区间dp入门
用f(i,j)表示将 i 到 j 一段合并所需要的最小代价，枚举中间的断点K转移
sum[i]表示前i个沙子的质量和，那么(l,r)的质量就是sum[r]-sum[l-1]
即\(f(i,j) = min\{f(i,k)+f(k+1,j)\}\)
用记忆化搜索写起来会比较方便
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define mod 998244353 #define N 100005 #define pi acos(-1) #define inf 0x7fffffff #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; int a[305],sum[305]; int f[305][305]; int dp(int l,int r) { if(f[l][r]!=-1)return f[l][r]; if(l==r)return 0; int ans=inf; for(int i=l;i<r;i++) ans=min(ans,dp(l,i)+dp(i+1,r)); return f[l][r]=(ans+sum[r]-sum[l-1]); } int main() { memset(f,-1,sizeof(f)); n=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i]; printf("%d\n",dp(1,n)); return 0; } |
Subscribe
计数器 9300536
OI 课件=>
OI 课件=>