7 条题解
-
2
区间DP
#include<bits/stdc++.h> using namespace std; int f[305][305],a[305],sum[305]; int main(){ int n; n=2;//两堆果子 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; }
信息
- ID
- 1
- 时间
- 1000ms
- 内存
- 64MiB
- 难度
- 1
- 标签
- (无)
- 递交数
- 706
- 已通过
- 359
- 上传者