区间DP AcWing 282. 石子合并

拼搏现实的明天。 2023-09-28 13:02 127阅读 0赞

## 区间DP AcWing 282. 石子合并 ##

### 原题链接 ###

[AcWing 282. 石子合并][AcWing 282.]

### 算法标签 ###

动态规划 区间DP

### 思路 ###

![在这里插入图片描述][600963c0968d44648fe9e78644d3736c.png]

### 代码 ###

#include<bits/stdc++.h>
    #define int long long
    #define rep(i, a, b) for(int i=a;i<b;++i)
    #define Rep(i, a, b) for(int i=a;i>b;--i)
    using namespace std;
    const int N = 505;
    int a[N], s[N], f[N][N];
    inline int read(){
       int s=0,w=1;
       char ch=getchar();
       while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
       while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
       return s*w;
    }
    void put(int x) {
        if(x<0) putchar('-'),x=-x;
        if(x>=10) put(x/10);
        putchar(x%10^48);
    }
    signed main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        int n=read();
        rep(i, 1, n+1){
            a[i]=read();
        }
        rep(i, 1, n+1){
            a[i]+=a[i-1];
        }
        // 石子堆长度 若石子堆长度为1 f[1][1]初始值0，符合题意  
        rep(len, 2, n+1){
        	// 石子堆起点
            for(int i=1; i+len-1<=n; ++i){
            	// 石子堆左右端点 
                int l=i, r=i+len-1;
                f[l][r]=1e8;
                // 石子分割点
                rep(k, l, r){
                    f[l][r]=min(f[l][r], f[l][k]+f[k][r]+s[r]-s[l-1]);
                }
            }
        }
        printf("%lld", f[1][n]);
        return 0;
    }

原创不易  
转载请标明出处  
如果对你有所帮助 别忘啦点赞支持哈  
![在这里插入图片描述][9cb4cb80a18345158f8a69e2f196e5b9.png]

[AcWing 282.]: https://www.acwing.com/problem/content/284/
[600963c0968d44648fe9e78644d3736c.png]: https://img-blog.csdnimg.cn/600963c0968d44648fe9e78644d3736c.png
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://img-blog.csdnimg.cn/9cb4cb80a18345158f8a69e2f196e5b9.png