疯狂的采药—洛谷

题目：


思路：
完全背包的模板，但是需要空间优化，否则过不了。
代码：

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        int m=sc.nextInt();
        int[] tt=new int[m];
        int[] v=new int[m];
        for (int i = 0; i < m; i++) {
            tt[i]=sc.nextInt();
            v[i]=sc.nextInt();
        }
        System.out.println(dp(t,m,tt,v));
    }

    private static int dp(int t,int m,int[] tt,int[] v) {
//        int[][] dp=new int[m][t+1];
//        for (int i = 0; i <= t; i++) {
//            dp[0][i]=i/tt[0]*v[0];
//        }
//        for (int i = 1; i < m; i++) {
//            for (int j = 0; j <= t; j++) {
//                for (int k = 0; k*tt[i]<=j ; k++) {
//                    dp[i][j]=Math.max(dp[i][j],dp[i-1][j-k*tt[i]]+k*v[i]);
//                }
//            }
//        }
        int [] dp=new int[1100000];
        for (int i = 0; i < m; i++) {
            for (int j =tt[i]; j <= t ; j++) {
                dp[j]=Math.max(dp[j],dp[j-tt[i]]+v[i]);
            }
        }
        return dp[t];
    }

}