7 条题解

  • 2
    @ 2023-5-13 13:24:40

    区间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
上传者