hihocoder75

https://hihocoder.com/contest/offers75/problems

题目1 : 工作城市分配
题目2 : 工作城市分配2
思路：DP

package l751;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int[][]a=new int[2*n][2];
        for(int i=0;i<2*n;i++) {
            a[i][0]=sc.nextInt();
            a[i][1]=sc.nextInt();
        }
        
        int[][]dp=new int[2*n][1+n];
        dp[0][0]=a[0][1];
        dp[0][1]=a[0][0];
        
        for(int i=1;i<2*n;i++) {
            for(int j=0;j<=n;j++){
                if(j==0) dp[i][j]=dp[i-1][j]+a[i][1];
                else dp[i][j]=Math.max(dp[i-1][j]+a[i][1], dp[i-1][j-1]+a[i][0]);
            }
        }
        
        System.out.println(dp[2*n-1][n]);
    }
}

package l752;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int[][]a=new int[3*n][3];
        for(int i=0;i<3*n;i++) {
            a[i][0]=sc.nextInt();
            a[i][1]=sc.nextInt();
            a[i][2]=sc.nextInt();
        }
        
        int[][][]dp=new int[3*n][1+n][1+n];
        dp[0][0][0]=a[0][2];
        dp[0][0][1]=a[0][1];
        dp[0][1][0]=a[0][0];
        
        for(int i=1;i<3*n;i++) {
            for(int j=0;j<=n;j++){
                for(int k=0;k<=n;k++) {
                    dp[i][j][k]=dp[i-1][j][k]+a[i][2];
                    if(j!=0) dp[i][j][k]=Math.max(dp[i][j][k], dp[i-1][j-1][k]+a[i][0]);
                    if(k!=0) dp[i][j][k]=Math.max(dp[i][j][k], dp[i-1][j][k-1]+a[i][1]);
                }
            }
        }
        
        System.out.println(dp[3*n-1][n][n]);
    }
}

题目4 : 栈的加强版
比赛一直想用线段树+interval stabbing，WA
看别人提交有更简单的方法：打个标记就好了，每次弹出的时候输出本来的值和在那个位置上的标记，然后标记下传。
如果inc不是从栈底开始的，还是可以用栈，只需要在相应位置打上减的标记

package l753;

import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int[] a = new int[200001], add = new int[200001];
        int p=1;
        
        for(int i=0;i<n;i++) {
            String s=sc.next();
            if("push".equals(s)) {
                a[p++]=sc.nextInt();
            } else if("inc".equals(s)) {
                int t=sc.nextInt(),v=sc.nextInt();
                add[t]+=v;
            } else {
                System.out.println(a[p-1]+add[p-1]);
                p--;
                add[p-1]+=add[p];  //把p位置的标记保留下来
                add[p]=0;
            }
        }
    }
}

线段树WA版

package l753;

import java.util.Scanner;
import java.util.Stack;

public class CopyOfMain {
    
    public static int[] bits = new int[100001], a = new int[100001];
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        
        Stack<Integer>st=new Stack<Integer>();
        for(int i=0;i<n;i++) {
            String s=sc.next();
            if("push".equals(s)) {
                st.push(sc.nextInt());
            } else if("inc".equals(s)) {
                int t=sc.nextInt(),v=sc.nextInt();
                add(1, v);
                add(t+1, -v);
                a[1]+=v;
                a[t+1]-=v;
            } else {
                int len=st.size();
                int idx=st.pop();
                System.out.println(idx+sum(len));
                add(len, -a[len]);
//              add(len-1, a[len]);
                a[len]=0;
//              a[len-1]+=a[len];
            }
        }
    }

    private static int sum(int i) {
        int res=0;
        while(i>0) {
            res+=bits[i];
            i-=lowbit(i);
        }
        return res;
    }

    private static void add(int i, int v) {
        while(i<bits.length) {
            bits[i]+=v;
            i+=lowbit(i);
        }
    }

    private static int lowbit(int i) {
        return i&(-i);
    }
}