2 条题解

  • 1
    @ 2023-5-13 13:22:09

    区间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
      @ 2023-4-20 18:31:26

      这是一道典型的区间动归

      #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
      上传者