2 条题解
-
1
区间DP
注意,将相邻的果子堆合并,意味着你不能贪心
设f[i][j]代表合并i~j之间堆的最小消耗
不妨从终点考虑问题,即结果为两个子区间合并的最小值再加上合并需要的代价即可。
枚举两个子区间,即枚举这个区间的中间点k,使这个区间被分为[i,k]和[k+1,j]两个区间,取一遍最小值加上合并的即为当前区间所求。
至于合并的代价,用前缀和即可。
#include<bits/stdc++.h> using namespace std; int f[305][305],a[305],sum[305]; int main(){ int n; scanf("%d",&n);//输入果子数 for(int i=1;i<=n;i++){ scanf("%d",&a[i]); sum[i]+=sum[i-1]+a[i];//前缀和加快速度 } for(int l=1;l<=n;l++){//注意,按照合并的堆数循环 for(int i=1;i<=n-l+1;i++){//小心越界 int j=l+i-1;//j通过i,l得到 if(i!=j)f[i][j]=INT_MAX;//设为最大(初始化) for(int k=i;k<j;k++){//枚举中间点 f[i][j]=min(f[i][k]+f[k+1][j]+sum[j]-sum[i-1],f[i][j]);//转移方程 } } } printf("%d\n",f[1][n]);//输出 return 0; }
-
1
这是一道典型的区间动归
#include <bits/stdc++.h> using namespace std; int s[1001],f[1001][1001],n; int dp(int l, int r) { if (l==r)return 0; if (f[l][r]!=INT_MAX)return f[l][r]; for(int i=l;i<r;i++) { f[l][r]=min(f[l][r],dp(l,i)+dp(i+1,r)+s[r]-s[l - 1]); } return f[l][r]; } int main() { cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)f[i][j]=INT_MAX; for(int i=1;i<=n;i++)cin>>s[i],s[i]+=s[i-1]; cout<<dp(1,n); return 0; }
- 1
信息
- ID
- 611
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 3
- 标签
- 递交数
- 60
- 已通过
- 27
- 上传者