头像

张昂之.




离线:4小时前


活动打卡代码 AcWing 1023. 买书

张昂之.
6小时前

朴素版本

import java.util.Scanner;
public class Main{
     static int[][] f=new int[5][1010];
     static int[] v={0,10,20,50,100};
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int m=sc.nextInt();

        f[0][0]=1;
        for(int i=1;i<=4;i++)
          for(int j=0;j<=m;j++)
          {
             f[i][j]=f[i-1][j];
             if(j>=v[i]) f[i][j]+=f[i][j-v[i]];
          }

           System.out.println(f[4][m]);
    }
}

一维优化

import java.util.Scanner;
public class Main{
     static int[] f=new int[1010];
     static int[] v={0,10,20,50,100};
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int m=sc.nextInt();

        f[0]=1;
        for(int i=1;i<=4;i++)
          for(int j=v[i];j<=m;j++)
          {
               f[j]+=f[j-v[i]];
          }

           System.out.println(f[m]);
    }
}


活动打卡代码 AcWing 1019. 庆功会

张昂之.
10小时前
import java.util.Scanner;
public class Main{
     static int[][] f=new int[510][6010];
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();

        for(int i=1;i<=n;i++)
        {
            int v=sc.nextInt();
            int w=sc.nextInt();
            int s=sc.nextInt();
            for(int j=0;j<=m;j++)
             for(int k=0;k<=s && k*v<=j;k++)
             {
                 f[i][j]=Math.max(f[i][j],f[i-1][j-k*v]+k*w);
             }
        }
        System.out.println(f[n][m]);
    }
}


活动打卡代码 AcWing 278. 数字组合

张昂之.
10小时前
import java.util.Scanner;
public class Main{
     static int[] f=new int[10010];
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();

        f[0]=1;
        for(int i=0;i<n;i++)
        {
            int v=sc.nextInt();
            for(int j=m;j>=v;j--)
             f[j]+=f[j-v];
        }
        System.out.println(f[m]);
    }
}


活动打卡代码 AcWing 1020. 潜水员

张昂之.
11小时前
import java.util.Scanner;
import java.util.Arrays;
public class Main{
     static int[][] f=new int[30][80];
     static int INF=0x3f3f3f;
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int V1=sc.nextInt();
        int V2=sc.nextInt();
        int n=sc.nextInt();

        for(int i=0;i<=25;i++) Arrays.fill(f[i],INF);
        f[0][0]=0;
        for(int i=1;i<=n;i++)
        {
            int v1=sc.nextInt();
            int v2=sc.nextInt();
            int w=sc.nextInt();
            for(int j=V1;j>=0;j--)
             for(int k=V2;k>=0;k--)
              f[j][k]=Math.min(f[j][k],f[Math.max(0,j-v1)][Math.max(0,k-v2)]+w);
        }
        System.out.println(f[V1][V2]);
    }
}



张昂之.
15小时前
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        String s1=sc.next();
        String s2=sc.next();

        if(check(s1)==check(s2)) System.out.println("GO");
        else System.out.println("STAY");
    }
    static int check(String s)
    {
        int res=1;
        for(int i=0;i<s.length();i++)
        {
            int cnt=(s.charAt(i)-'A')+1;
            res=(res*cnt)%47;
        }
        return res;
    }
}


活动打卡代码 AcWing 1371. 货币系统

张昂之.
15小时前

朴素dp

import java.util.Scanner;
public class Main{
     static long[][] f=new long[30][10010];
     static int[] w=new int[30];
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();

        for(int i=1;i<=n;i++) w[i]=sc.nextInt();

        f[0][0]=1;

        for(int i=1;i<=n;i++)
         for(int j=0;j<=m;j++)
         {
             for(int k=0;k*w[i]<=j;k++)
              f[i][j]+=f[i-1][j-k*w[i]];
         }
         System.out.println(f[n][m]);
    }
}

优化

import java.util.Scanner;
public class Main{
     static long[] f=new long[10010];
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();

        f[0]=1;
        for(int i=1;i<=n;i++)
        {
          int v=sc.nextInt();
          for(int j=v;j<=m;j++)
              f[j]+=f[j-v];
         }
         System.out.println(f[m]);
    }
}



张昂之.
16小时前
import java.util.Scanner;
public class Main{
     static int[][] f=new int[1010][1010];
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int V=sc.nextInt();
        int M=sc.nextInt();

        for(int i=1;i<=n;i++)
        {
            int v=sc.nextInt();
            int m=sc.nextInt();
            int w=sc.nextInt();
            for(int j=V;j>=v;j--)
             for(int k=M;k>=m;k--)
              f[j][k]=Math.max(f[j][k],f[j-v][k-m]+w);
        }
        System.out.println(f[V][M]);
    }
}



张昂之.
16小时前

二维费用背包问题

import java.util.Scanner;
public class Main{
     static int[][] f=new int[1010][1010];
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int V1=sc.nextInt();
        int V2=sc.nextInt();
        int n=sc.nextInt();
        for(int i=1;i<=n;i++)
        {
            int v1=sc.nextInt();
            int v2=sc.nextInt();
            for(int j=V1;j>=v1;j--)
             for(int k=V2-1;k>=v2;k--)
              f[j][k]=Math.max(f[j][k],f[j-v1][k-v2]+1);
        }
        int x=V2-1;
        while(x>0 && f[V1][V2-1]==f[V1][x-1]) x--;

        System.out.println(f[V1][V2-1]+" "+(V2-x));
    }
}


活动打卡代码 AcWing 1024. 装箱问题

import java.util.Scanner;
public class Main{
     static int[] v=new int[20010];
     static int[] f=new int[20010];
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int m=sc.nextInt();
        int n=sc.nextInt();
        for(int i=1;i<=n;i++) v[i]=sc.nextInt();

        for(int i=1;i<=n;i++)
         for(int j=m;j>=v[i];j--)
         {
             f[j]=Math.max(f[j],f[j-v[i]]+v[i]);
         }
         System.out.println(m-f[m]);
}
}


活动打卡代码 AcWing 423. 采药

import java.util.Scanner;
public class Main{
     static int[] v=new int[1010];
     static int[] w=new int[1010];
     static int[] f=new int[1010];
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int m=sc.nextInt();
        int n=sc.nextInt();
        for(int i=1;i<=n;i++)
        {
            v[i]=sc.nextInt();
            w[i]=sc.nextInt();
        }

        for(int i=1;i<=n;i++)
         for(int j=m;j>=v[i];j--)
         {
            f[j]=Math.max(f[j],f[j-v[i]]+w[i]);
         }
         System.out.println(f[m]);
    }
}