3097164_ac_328ms_4880k.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.*;

public class Main 
{
	static final int INF = -2100000000;

    public static void main(String [] args)
    {
		new Main().solve();
    }

	private void solve()
	{
		Scanner cin = new Scanner (System.in);
		int cas;
		int i, j, k, m, n;
		int [][] p = new int [101][101];
		int rew[] = new int [101];
		int pun[] = new int [101];
		int salary, max, ans, cnt, tmp;
		int dp[][] = new int [101][101];
		int cost[][] = new int [101][101];
		int num[] = new int [101];

		cas = cin.nextInt();
		while(cas-- > 0)
		{
			m = cin.nextInt();
			n = cin.nextInt();
			salary = cin.nextInt();
			for(i = 0; i < m; i++)
			{
				p[i][0] = 0;
				for(j = 1; j <= n; j++)
				{
					p[i][j] = cin.nextInt();
				}
				rew[i] = cin.nextInt();
				pun[i] = cin.nextInt();
			}
			for(i = 0; i < m; i++)
			{
				for(j = 0; j <= n; j++)
				{
					cost[i][j] = p[i][j]*(rew[i]-salary*j)-(100-p[i][j])*pun[i];
				}
			}
			for(i = 0; i <= n; i++)
			{
				dp[0][i] = cost[0][i];
			}
			for(i = 1; i < m; i++)
			{
				for(j = 0; j <= n; j++)
				{
					max = INF;
					for(k = 0; k <= j; k++)
					{
						tmp = dp[i-1][k] + cost[i][j-k];
						if(tmp > max)
						{
							max = tmp;
						}
					}
					dp[i][j] = max;
				}
			}
			ans = INF;
			cnt = 0;
			for(i = 0; i <= n; i++)
			{
				if(dp[m-1][i] > ans)
				{
					num[0] = i;
					cnt = 1;
					ans = dp[m-1][i];
				}
				else
				{
					if(dp[m-1][i] == ans)
					{
						num[cnt++] = i;
					}
				}
			}
			System.out.println(ans);
			System.out.print(num[0]);
			for(i = 1; i < cnt; i++)
			{
				System.out.print(" "+num[i]);
			}
			System.out.println();
		}
	}
}