蓝桥杯官网 试题 PREV-274 历届真题 分果果【第十二届】【省赛】【研究生组】【C++】【Java】两种解法

//动态规划做的
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 105
int n,m;
int w[N],sum[N],dp[N][N][N];
int ans=0x7f7f7f7f,tot=0,maxw=0;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&w[i]);
		tot+=w[i];
		maxw=max(maxw,w[i]);
		sum[i]=sum[i-1]+w[i];
	}
	if(m==1){
		printf("0\n");return 0;
	}
	int max_sum=tot*2/(m-1);
	maxw=max(maxw,max_sum/2);
	for(int max_v=max_sum;max_v>=maxw;max_v--){
		memset(dp,0,sizeof(dp));
		dp[0][0][0]=max_v;
		for(int i=1;i<=m;i++){
			for(int j=1;j<=n;j++){
				for(int k=0;k<=j;k++){
					dp[i][j][k]=dp[i][j][k-1];
					for(int kk=k;kk>=0;kk--){
						if(sum[j]-sum[kk]<=max_v){
							dp[i][j][k]=max(dp[i][j][k],min(dp[i-1][k][kk],sum[j]-sum[kk]));
							if(i==m&&j==n)ans=min(ans,max_v-dp[i][j][k]);
						}
						else break;
					}
				}
			}
		}
	}

	printf("%d\n",ans);

}

import java.io.*;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) { new Main().run(); }
 
    int INF = 0x3F3F3F3F;
 
    void run() {
        InputReader in = new InputReader(System.in);
        int n = in.readInt(), m = in.readInt(), ans = INF;
        int[][][] dp = new int[m + 1][n + 1][n + 1];
        int[] S = new int[n + 1];
        for (int i = 1; i <= n; i++)
            S[i] = S[i - 1] + in.readInt();
        for (int i = 0; i <= m; i++)
            for (int j = 0; j <= n; j++)
                for (int k = 0; k <= j; k++) dp[i][j][k] = INF;
        dp[0][0][0] = 0;
        for (int min = S[n] * 2 / m; min > 0; min--) {
            for (int i = 1; i <= m; i++)
                for (int j = 1; j <= n; j++) {
                    int trans2 = 0, trans3 = 0;
                    for (int k = 1; k <= j; k++) {
                        dp[i][j][k] = dp[i][j][k - 1];
                        while (trans2 < k && S[j] - S[trans2 + 1] >= min &&
                                max(dp[i - 1][trans2 + 1][trans2 + 1], S[j] - S[trans2 + 1]) <= max(dp[i - 1][trans2][trans2], S[j] - S[trans2])) trans2++;
                        if (S[j] - S[trans2] >= min)
                            dp[i][j][k] = min(dp[i][j][k], max(dp[i - 1][trans2][trans2], S[j] - S[trans2]));
                        while (trans3 < k && S[j] - S[trans3 + 1] >= min &&
                                max(dp[i - 1][k][trans3 + 1], S[j] - S[trans3 + 1]) <= max(dp[i - 1][k][trans3 + 1], S[j] - S[trans3])) trans3++;
                        if (S[j] - S[trans3] >= min)
                            dp[i][j][k] = min(dp[i][j][k], max(dp[i - 1][k][trans3], S[j] - S[trans3]));
                    }
                }
            ans = min(ans, dp[m][n][n] - min);
        }
        System.out.println(ans);
    }
 
    int max(int arg1, int arg2) { return arg1 > arg2 ? arg1 : arg2; }
 
    int min(int arg1, int arg2) { return arg1 < arg2 ? arg1 : arg2; }
 
    class InputReader {
 
        BufferedReader reader;
        StringTokenizer token;
 
        InputReader(InputStream in) {
            this.reader = new BufferedReader(new InputStreamReader(in));
        }
 
        String read() {
            while (token == null || !token.hasMoreTokens()) {
                try {
                    token = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return token.nextToken();
        }
 
        int readInt() { return Integer.parseInt(read()); }
    }
}