头像

千禾




在线 


活动打卡代码 AcWing 1064. 小国王

千禾
2小时前
import java.util.*;
public class Main{
    static int N = 12, M = 1<<10, K = 110, n, m;
    static long f[][][] = new long[N][K][M]; 
    static int cnt[] = new int[M];
    static ArrayList<Integer> state = new ArrayList<Integer>();
    static ArrayList<Integer> match[] = new ArrayList[M];

    static boolean check(int x){
        for(int i = 0; i < n; i ++){
            if( (x>>i&1) == 1 && (x>>(i+1)&1 ) == 1) return false;
        }
        return true;
    }
    static int count(int x){
        int res = 0;
        for(int i = 0; i < n; i ++){
            if( (x>>i&1) == 1) res++;
        }
        return res;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i = 0 ; i < 1<<n ; i ++){
            match[i] = new ArrayList();
            if(check(i)){
                state.add(i);
                cnt[i] = count(i);
            }
        }
        for(int i = 0; i < state.size(); i ++){
            for(int j = 0; j < state.size(); j ++){
                int a = state.get(i);
                int b = state.get(j);
                if( (a&b) == 0 && check(a | b)) match[i].add(j);
            }
        }
        f[0][0][0] = 1;
        for(int i = 1; i <= n +1; i ++){
            for(int j = 0; j <= m; j ++){
                for(int a = 0; a < state.size(); a ++){
                    for(int b : match[a]){
                        int c = cnt[state.get(a)];
                        if(j >= c) f[i][j][state.get(a)] += f[i - 1][j - c][state.get(b)];
                    }
                }
            }
        }
        System.out.println(f[n+1][m][0]);
    }
}


活动打卡代码 AcWing 1058. 股票买卖 V

千禾
7小时前
import java.util.*;
public class Main{
    static int N = 100010, INF = 0x3f3f3f3f;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int w[] = new int[N];
        int f[][] = new int[N][3];
        f[0][1] = f[0][0] = -INF;
        int n = sc.nextInt();
        for(int i = 1; i <= n; i ++) w[i] = sc.nextInt();
        for(int i = 1; i <= n; i ++) {
            f[i][1] = f[i-1][0] + w[i];
            f[i][0] = Math.max(f[i-1][0], f[i-1][2] - w[i]);
            f[i][2] = Math.max(f[i-1][1], f[i-1][2]);
        }
        System.out.println(Math.max(f[n][2], f[n][1]) );
    }
}


活动打卡代码 AcWing 1049. 大盗阿福

千禾
8小时前
import java.util.*;
public class Main{
    static int N = 100010;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while(T-- != 0){
            int n = sc.nextInt();
            int a[] = new int[N];
            int f[][] = new int[N][3];
            for(int i = 1; i <= n; i ++) a[i] = sc.nextInt();
            f[1][0] = 0;
            f[1][1] = a[1];
            for(int i = 2; i <= n; i ++){
                f[i][0] = Math.max(f[i-1][0], f[i-1][1]);
                f[i][1] = Math.max(f[i][1], f[i-1][0] + a[i]);
            }
            System.out.println(Math.max(f[n][0], f[n][1]));
        }
    }
}
####    一维
    f[i] = Math.max(f[i-1], f[i-2] + w[i]);
####    二维状态机
    f[i][0] = Math.max(f[i-1][0], f[i-1][1]);
    f[i][1] = Math.max(f[i][1], f[i-1][0] + a[i]);


活动打卡代码 AcWing 734. 能量石

千禾
9小时前
/*
按照贪心思路推出相邻两项的公式  S[i] * L[i+1] ----- L[i] * S[i-1], 依次排序先选最小的,
f[i, j] 表示在前i项能量石里选,且总时间恰好是j的最大收益;  不选 : f[i-1, j];选:f[i-1, j - s] + e-(j-s)*l;
*/
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int C = 1; C <= T; C ++){
            int f[] = new int[10010];
            Node q[] = new Node[110];
            int n = sc.nextInt(), m = 0;
            for(int i = 0; i < n; i ++){
                int s = sc.nextInt();
                int e = sc.nextInt();
                int l = sc.nextInt();
                m += s;
                q[i] = new Node(s, e, l);
            }
            Arrays.sort(q, 0, n);
            Arrays.fill(f, -0x3f3f3f3f);
            f[0] = 0;
            for(int i = 0; i < n; i ++){
                int s = q[i].s , e = q[i].e, l = q[i].l;
                for(int j = m; j >= s; j --)
                    f[j] = Math.max(f[j], f[j - s] + e-(j-s)*l);
            }
            int res = 0;
            for(int i = 0; i <= m; i ++) res = Math.max(res, f[i]);
            System.out.println("Case #"+C+": "+res);
        }
    }
    static class Node implements Comparable<Node>{
        int s, e, l;
        Node(int a, int b, int c){
            s = a; e = b; l = c;
        }
        public int compareTo(Node n){
            return  (s * n.l) - (n.s * l);
        }
    }
}



千禾
19小时前
import java.util.*;
public class Main{
    static int N = 110, n, m;
    static int w[] = new int[N], v[] = new int[N],  f[][] = new int[N][N];
    static int e[] = new int[N], ne[] = new int[N], h[] = new int[N],idx;
    static void dfs(int u){
        for(int i = v[u]; i <= m; i ++) f[u][i] = w[u];
        for(int i = h[u]; i != -1; i = ne[i]){
            int son = e[i];  //  对于每个子节点都有选和不选两种;
            dfs(son);
            for(int j = m; j >= v[u]; j --){  //  
                for(int k = j - v[u]; k >= 0; k --)
                    f[u][j] = Math.max(f[u][j], f[u][j - k] + f[son][k]);
            }
        }
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        Arrays.fill(h, -1);
        n = sc.nextInt();
        m = sc.nextInt();
        int root = 0;
        for(int i = 1; i <= n; i ++){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
            int p = sc.nextInt();
            if(p == -1) root = i;
            else add(p, i);
        }
        dfs(root);
        System.out.println(f[root][m]);
    }
    static void add(int a, int b){
        e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
    }
}



千禾
19小时前
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int mod = 1000000000+7;
        int N = 1010;
        int f[] = new int[N];
        int g[] = new int[N];
        Arrays.fill(f, -0x3f3f3f3f);
        f[0] = 0;
        g[0] = 1;
        for(int i = 0; i < n; i ++){
            int v = sc.nextInt();
            int w = sc.nextInt();
            for(int j = m; j >= v; j --){
                int max = Math.max(f[j], f[j - v] + w);
                int cnt = 0;
                if(max == f[j]) cnt = (cnt + g[j]) % mod;
                if(max == f[j - v] + w) cnt = (cnt + g[j-v]) % mod;
                g[j] = cnt;
                f[j] = max;
            }
        }
        int res = 0, max = 0;
        for(int i = 0; i <= m; i ++) max = Math.max(max, f[i]);
        for(int i = 0; i <= m; i ++){
            if(max == f[i]) res = (res + g[i]) % mod;
        }
        System.out.println(res);
    }
}


活动打卡代码 AcWing 7. 混合背包问题

千禾
1天前
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int f[] = new int[1010];
        for(int i = 0; i < n; i ++){
            int v = sc.nextInt();
            int w = sc.nextInt();
            int s = sc.nextInt();
            if(s == 0){
                for(int j = v; j <= m ;j ++) f[j] = Math.max(f[j], f[j - v] + w);
            }else{
                if(s == -1) s = 1;
                for(int k = 1; k < s; k *= 2){
                    for(int j = m; j >= v*k; j --)
                        f[j] = Math.max(f[j], f[j - v*k] + w*k);
                    s -= k;
                }
                if(s > 0){
                    for(int j = m ; j >= v*s; j --){
                        f[j] = Math.max(f[j], f[j - v*s] + w*s);
                    }
                }
            }
        }
        System.out.println(f[m]);
    }
}


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

千禾
1天前
import java.util.*;
public class Main{
    static int N = 110, M = 25010;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while(T -- != 0){
            int n = sc.nextInt();
            int a[] = new int[N];
            for(int i = 0; i < n; i ++) a[i] = sc.nextInt();
            Arrays.sort(a, 0, n);
            int f[] = new int[M];
            f[0] = 1;
            int res = 0;
            for(int i = 0; i < n; i ++){
                if(f[a[i]] == 0) res++;
                for(int j = a[i]; j <= a[n-1]; j ++){
                    f[j] += f[j - a[i]];
                }
            }
            System.out.println(res);
        }
    }
}


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

千禾
1天前
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        long f[] = new long[m + 1];
        f[0] = 1;
        for(int i = 0; i < n; i ++){
            int a = sc.nextInt();
            for(int j = a; j <= m; j ++){
                f[j] += f[j - a];
            }
        }
        System.out.println(f[m]);
    }
}


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

千禾
1天前
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        long f[] = new long[3010];
        int n = sc.nextInt();
        int m = sc.nextInt();
        int a[] = new int[20];
        f[0] = 1;
        for(int i = 1; i <= n; i ++) a[i] = sc.nextInt();
        for(int i = 1; i <= n; i ++){
            for(int j = a[i]; j <= m; j ++){
                f[j] += f[j - a[i]];
            }
        }
        System.out.println(f[m]);
    }
}