初始化问题
查看原帖
初始化问题
1211502
TearsMeow楼主2024/11/8 23:56

我做初始化了,为什么答案一直是0,我找了好久的错

二维费用的背包问题,我想先求一下最小的时间花费。我写三维就能过样例(TLE了)有没有佬说下,难道这道题不能这样初始化吗

public class Main {
    static int N = 1010,n,m,r,INF = 0xffffff;
    static int[][] f = new int[N][N];
    static int Int(String s){return Integer.parseInt(s);}
    static int[] rmb = new int[N],t = new int[N],rp = new int[N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args)throws IOException{
        String[] arrStr = br.readLine().split(" ");
        n = Int(arrStr[0]);
        for(int i = 1;i <= n;i++){
            arrStr = br.readLine().split(" ");
            //钱,人品,时间
            rmb[i] = Int(arrStr[0]);rp[i] = Int(arrStr[1]);
            t[i] = Int(arrStr[2]);
        }
        arrStr = br.readLine().split(" ");
        m = Int(arrStr[0]);r = Int(arrStr[1]);
        //初始化
        for(int i =0;i <= n;i++) Arrays.fill(f[i],INF);
        f[0][0] = 0;
        for(int i = 1;i <= n;i++) {
        	for(int j = m;j >= rmb[i]; j --) {
        		for(int k = r;k >= rp[i];k --) {
        			f[j][k]= Math.min(f[j - rmb[i]][k - rp[i]] + t[i] , f[j][k]); 
        		}
        	}
        }
        pw.println(f[m][r]);
        pw.flush();br.close();pw.close();
    }
}

2024/11/8 23:56
加载中...