import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static int[] sub = new int[201];
    public static int[] sum = new int[201];
    public static int[][] f = new int[21][801];
    public static ArrayList[][] path = new ArrayList[21][801];
    public static int n, m, Case, i, j, k, x, ans,temp,sumD,sumP,d,p;

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        for (i = 0; i < 21; i++) for (j = 0; j < 801; j++) path[i][j] = new ArrayList<Integer>();
        for (Case = 0; cin.hasNext(); ) {
            n = cin.nextShort();
            m = cin.nextShort();
            if (n + m == 0) break;
            for (i = 0; i < 21; i++) for (j = 0; j < 801; j++) path[i][j].clear();
            for (i = 0; i < 21; i++) for (j = 0; j < 801; j++) f[i][j] = -1;
            for (i = 1; i <= n; i++) {
                d = cin.nextShort();
                p = cin.nextShort();
                sub[i] = d - p;
                sum[i] = d + p;
            }
            ans = 20 * m;
            f[0][ans] = 0;
            for (k = 1; k <= n; k++)//选择一个
                for (i = m - 1; i >= 0; i--)//进行逆推
                    for (j = 0; j < 2 * ans; j++) {
                        if (f[i][j] >= 0) {
                            if (f[i + 1][j + sub[k]] <= f[i][j] + sum[k]) {
                                f[i + 1][j + sub[k]] = f[i][j] + sum[k];
                                path[i + 1][j + sub[k]].addAll(path[i][j]);
                                path[i + 1][j + sub[k]].add(k);
                            }
                        }
                    }
            for (x = 0; f[m][ans + x] == -1 && f[m][ans - x] == -1; x++) ;
            temp = (f[m][ans + x] > f[m][ans - x]) ? x : -x;
            sumD = (f[m][ans + temp] + temp) / 2;
            sumP = (f[m][ans + temp] - temp) / 2;
            System.out.println("Jury #" + (++Case));
            System.out.println("Best jury has value " + sumD + " for prosecution and value " + sumP + " for defence:");
            for (i = 0; i < m; i++) System.out.print(" " + path[m][ans + temp].get(i));
            System.out.println("\n");
        }
    }
}

---------------------------------------------------------------------

#include<vector>
#include<cstdio>
#include<iostream>
using namespace std;
int dp[21][801];
vector<int> path[21][801];
int sub[201],sum[201],Case,n,m;
int main() {
	while(~scanf("%d%d",&n,&m) && n && m) {
		for(int i=0; i<21; i++)for(int j=0; j<801; j++)path[i][j].clear();//清空vector
		for(int i=0; i<21; i++)for(int j=0; j<801; j++)dp[i][j]=-1;
		for(int i = 1,d,p; i <= n; i++) cin>>d>>p,sub[i] = d-p,sum[i] = d+p;
		int ans = 20*m,x;
		dp[0][ans] = 0;
		int time1=0;
		for(int k = 1; k <= n; k++)//选择一个
			for(int i = m-1; i >= 0; i--)//进行逆推
				for(int j = 0; j < 2*ans; j++) {
					if(dp[i][j] >= 0) {
						if(dp[i+1][j+sub[k]] <= dp[i][j] + sum[k]) {
							dp[i+1][j+sub[k]] = dp[i][j] + sum[k];
							path[i+1][j+sub[k]] = path[i][j];//每次更新都要把path全部复制过来，就是因为这个才用的vector
							path[i+1][j+sub[k]].push_back(k);
						}
					}
				}
		for(x = 0; dp[m][ans+x] == -1 && dp[m][ans-x] == -1; x++);
		int temp = (dp[m][ans+x] > dp[m][ans-x]) ? x : -x;
		int sumD = (dp[m][ans+temp] + temp )/2;
		int sumP = (dp[m][ans+temp] - temp )/2;

		printf( "Jury #%d\n",++Case);
		printf( "Best jury has value %d for prosecution and value %d for defence:\n", sumD,sumP);
		for(int i=0; i < m; i++ )printf( " %d", path[m][ans+temp][i]);
		printf( "\n\n" );
	}
	return 0;
}

• Re:为什么同样的代码Java会MLE，C++就跑得欢乐？WHY？ (3798) sbqdd 2021-06-16 19:15:50