2750027_re.java

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

import java.util.*;

public class Main
{
	public static void main(String[] args)  throws Exception 
	{
		Scanner cin = new Scanner(System.in);
		int i, j, k, d, n;
		int inf = 100000000;
		int dis[] = new int [102];
		int f[][] = new int [102][201];
		int sta[] = new int [102];
		int pri[] = new int [102];
		
		d = cin.nextInt();
		n = 1;
		while(cin.hasNext())
		{
			sta[n] = cin.nextInt();
			pri[n] = cin.nextInt();
			n++;
		}
		sta[n] = d;sta[0] = 0;
		for (i = 0; i <= n; i++)
		{
			dis[i] = sta[i]-sta[i-1];
			if (dis[i]>200||(i==1||i==n)&&dis[i]>100 || n==1 && dis[i]>0)
			{
				System.out.println("Impossible");
				return ;
			}
			for (j = 0; j < 200; j++)
				f[i][j] = inf;
		}
		f[1][100-sta[1]] = 0;
	    for (i = 1; i < n; i++)
	    {
	        for(j = 0; j <= 200; j++)
	        {
	            if(f[i][j]!=inf)
	            {
	                for(k=0; k<=200-j; k++)
	                {
	                    if(j+k>=dis[i+1] && f[i][j]+k*pri[i]<f[i+1][j+k-dis[i+1]])
	                    {
	                        f[i+1][j+k-dis[i+1]] = f[i][j]+k*pri[i];
	                    }
	                }
	            }
	        }
	    }
	    System.out.println(f[n][100]);
	}

}