头像

思思入扣




离线:22小时前



思思入扣
23小时前

最长上升子序列 II

给定一个长度为N的数列,求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数N。

第二行包含N个整数,表示完整序列。

输出格式

输出一个整数,表示最大长度。

数据范围

1≤N≤100000,
−109≤数列中的数≤109

输入样例:

7
3 1 2 1 8 5 6

输出样例:

4

分析

import java.util.Scanner;

public class Main {

    private static final int N=100010;
    private static int n;
    private static int[] a=new int[N],q=new int[N];//q:所有不同长度的上升子序列结尾的最小值

    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        n=scanner.nextInt();
        for(int i=0;i<n;i++)
            a[i]=scanner.nextInt();
        int len=0;//当前的最大长度,(q里面的元素个数)
        for(int i=0;i<n;i++){
            int l=0,r=len;
            while (l<r){
                int mid=l+r+1 >>1;//上取整,需要加1
                if(q[mid]<a[i])//在右边
                    l=mid;
                else r=mid-1;//在左边
            }
            len=Math.max(len,r+1);//更新最大值,接完长度回加1,所有需要用加1来更新len
            q[r+1]=a[i];//把q跟新a[i]
        }
        System.out.println(len);
    }
}



思思入扣
23小时前
import java.util.Scanner;

public class Main {

    private static final int N=100010;
    private static int n;
    private static int[] a=new int[N],q=new int[N];//q:所有不同长度的上升子序列结尾的最小值

    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        n=scanner.nextInt();
        for(int i=0;i<n;i++)
            a[i]=scanner.nextInt();
        int len=0;//当前的最大长度,(q里面的元素个数)
        for(int i=0;i<n;i++){
            int l=0,r=len;
            while (l<r){
                int mid=l+r+1 >>1;//上取整,需要加1
                if(q[mid]<a[i])//在右边
                    l=mid;
                else r=mid-1;//在左边
            }
            len=Math.max(len,r+1);//更新最大值,接完长度回加1,所有需要用加1来更新len
            q[r+1]=a[i];//把q跟新a[i]
        }
        System.out.println(len);
    }
}



整数划分

一个正整数n可以表示成若干个正整数之和,形如:n=n1+n2+…+nk,其中n1≥n2≥…≥nk,k≥1。

我们将这样的一种表示称为正整数n的一种划分。

现在给定一个正整数n,请你求出n共有多少种不同的划分方法。

输入格式

共一行,包含一个整数n。

输出格式

共一行,包含一个整数,表示总划分数量。

由于答案可能很大,输出结果请对109+7取模。

数据范围

1≤n≤1000

输入样例:

5

输出样例:

7

分析

思路和完全背包一样

import java.util.Scanner;

public class Main {
    private static int N=1010,mod=(int)(1e9 + 7);
    private static int n;
    private static int[] f=new int[N];
    private static int[][] f1=new int[N][N];

    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        n=scanner.nextInt();
        int res=dp1();
        System.out.println(res);

    }

    //优化:[j] = f[j] + f[j - i]
    private static int dp1() {
        f[0]=1;//一个数都不选的时候总和是0,方案是1,其余的方案都是0
        //完全背包写法
        for(int i=1;i<=n;i++){
            for(int j=i;j<=n;j++)
                f[j]=(f[j] + f[j-i]) % mod;
        }
        return f[n];
    }

    //未优化:f[i][j] = f[i - 1][j - 1] + f[i - j][j]
    private static int dp2() {
        f1[1][1]=1;
        for(int i=2;i<=n;i++)
            for(int j=1;j<=i;j++)
                f1[i][j]=(f1[i-1][j-1]+f1[i-j][j])%mod;

        int res=0;
        for(int i=1;i<=n;i++)
            res=(res+f1[n][i])%mod;
        return res;
    }
}


活动打卡代码 AcWing 900. 整数划分

import java.util.Scanner;

public class Main {
    private static int N=1010,mod=(int)(1e9 + 7);
    private static int n;
    private static int[] f=new int[N];
    private static int[][] f1=new int[N][N];

    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        n=scanner.nextInt();
        int res=dp1();
        System.out.println(res);

    }

    //优化:[j] = f[j] + f[j - i]
    private static int dp1() {
        f[0]=1;//一个数都不选的时候总和是0,方案是1,其余的方案都是0
        //完全背包写法
        for(int i=1;i<=n;i++){
            for(int j=i;j<=n;j++)
                f[j]=(f[j] + f[j-i]) % mod;
        }
        return f[n];
    }

    //未优化:f[i][j] = f[i - 1][j - 1] + f[i - j][j]
    private static int dp2() {
        f1[1][1]=1;
        for(int i=2;i<=n;i++)
            for(int j=1;j<=i;j++)
                f1[i][j]=(f1[i-1][j-1]+f1[i-j][j])%mod;

        int res=0;
        for(int i=1;i<=n;i++)
            res=(res+f1[n][i])%mod;
        return res;
    }
}



滑雪

给定一个R行C列的矩阵,表示一个矩形网格滑雪场。

矩阵中第 i 行第 j 列的点表示滑雪场的第 i 行第 j 列区域的高度。

一个人从滑雪场中的某个区域内出发,每次可以向上下左右任意一个方向滑动一个单位距离。

当然,一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。

下面给出一个矩阵作为例子:

1 2 3 4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9
在给定矩阵中,一条可行的滑行轨迹为24-17-2-1。

在给定矩阵中,最长的滑行轨迹为25-24-23-…-3-2-1,沿途共经过25个区域。

现在给定你一个二维矩阵表示滑雪场各区域的高度,请你找出在该滑雪场中能够完成的最长滑雪轨迹,并输出其长度(可经过最大区域数)。

输入格式

第一行包含两个整数R和C。

接下来R行,每行包含C个整数,表示完整的二维矩阵。

输出格式

输出一个整数,表示可完成的最长滑雪长度。

数据范围

1≤R,C≤300,
0≤矩阵中整数≤10000

输入样例:

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

输出样例:

25

分析

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    private static int N=310;
    private static int n,m;
    private static int[][] g=new int[N][N];//每个点的高度
    private static int[][] f=new int[N][N];//状态
    private static int[] dx=new int[]{-1,0,1,0},dy=new int[]{0,1,0,-1};

    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        n=scanner.nextInt();
        m=scanner.nextInt();
        for(int i=1;i<=n;i++){//读入每个点的高度
            for(int j=1;j<=m;j++)
                g[i][j]=scanner.nextInt();
        }
        for(int i=1;i<=n;i++)//初始化为-1,表示每个状态都没有被算过
            Arrays.fill(f[i],-1);
        int res=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++)
                res=Math.max(res,dp(i,j));//dp(i,j)返回的是(i,j)的状态
        }
        System.out.println(res);
        scanner.close();
    }

    private static int dp(int x, int y) {
        if(f[x][y]!=-1)//判定是否算过
            return f[x][y];
        f[x][y]=1;
        for(int i=0;i<4;i++){
            int a=x+dx[i];
            int b=y+dy[i];
            if(a>=1 && a<=n && b>=1 && b<=m && g[x][y]>g[a][b])//判断是否在界限内
                f[x][y]=Math.max(f[x][y],dp(a,b)+1);
        }
        return f[x][y];
    }
}


活动打卡代码 AcWing 901. 滑雪

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    private static int N=310;
    private static int n,m;
    private static int[][] g=new int[N][N];//每个点的高度
    private static int[][] f=new int[N][N];//状态
    private static int[] dx=new int[]{-1,0,1,0},dy=new int[]{0,1,0,-1};

    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        n=scanner.nextInt();
        m=scanner.nextInt();
        for(int i=1;i<=n;i++){//读入每个点的高度
            for(int j=1;j<=m;j++)
                g[i][j]=scanner.nextInt();
        }
        for(int i=1;i<=n;i++)//初始化为-1,表示每个状态都没有被算过
            Arrays.fill(f[i],-1);
        int res=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++)
                res=Math.max(res,dp(i,j));//dp(i,j)返回的是(i,j)的状态
        }
        System.out.println(res);
        scanner.close();
    }

    private static int dp(int x, int y) {
        if(f[x][y]!=-1)//判定是否算过
            return f[x][y];
        f[x][y]=1;
        for(int i=0;i<4;i++){
            int a=x+dx[i];
            int b=y+dy[i];
            if(a>=1 && a<=n && b>=1 && b<=m && g[x][y]>g[a][b])//判断是否在界限内
                f[x][y]=Math.max(f[x][y],dp(a,b)+1);
        }
        return f[x][y];
    }
}



没有上司的舞会

Ural大学有N名职员,编号为1~N。

他们的关系就像一棵以校长为根的树,父节点就是子节点的直接上司。

每个职员有一个快乐指数,用整数 Hi 给出,其中 1≤i≤N。

现在要召开一场周年庆宴会,不过,没有职员愿意和直接上司一起参会。

在满足这个条件的前提下,主办方希望邀请一部分职员参会,使得所有参会职员的快乐指数总和最大,求这个最大值。

输入格式

第一行一个整数N。

接下来N行,第 i 行表示 i 号职员的快乐指数Hi。

接下来N-1行,每行输入一对整数L, K,表示K是L的直接上司。

输出格式

输出最大的快乐指数。

数据范围

1≤N≤6000,
−128≤Hi≤127

输入样例:

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5

输出样例:

5

分析

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    private static int N=6010;
    private static int n,idx;
    private static int[] h=new int[N],e=new int[N],ne=new int[N];//邻接表存
    private static int[] happy=new int[N];//高兴度
    private static int[][] f=new int[N][2];//所有状态
    private static boolean[] has_fa=new boolean[N];//判断每个节点是否有根节点

    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        n=scanner.nextInt();
        for(int i=1;i<=n;i++)
            happy[i]=scanner.nextInt();
        Arrays.fill(h,-1);//表头初始化为-1
        for(int i=0;i<n-1;i++){//读入每条边
            int a,b;
            a=scanner.nextInt();
            b=scanner.nextInt();
            has_fa[a]=true;//b是a的父节点,所以a就有父节点了
            add(b,a);
        }
        int root=1;
        while (has_fa[root])//如果有父节点,看下一个点,直到没有父节点为止
            root++;
        dfs(root);
        //f[root][0]:不选根节点,f[root][1]:选择根节点
        System.out.println(Math.max(f[root][0],f[root][1]));

    }

    //邻接表插入一条边
    private static void add(int a, int b) {
        e[idx]=b;
        ne[idx]=h[a];
        h[a]=idx++;
    }

    //求每个状态
    private static void dfs(int u) {
        f[u][1]=happy[u];//选择这个点,需要加上高兴度
        for(int i=h[u];i!=-1;i=ne[i]){//再枚举所有儿子
            int j=e[i];//j表示u的某个儿子
            dfs(j);//先递归算
            f[u][0]+=Math.max(f[j][0],f[j][1]);
            f[u][1]+=f[j][0];
        }
    }
}



import java.util.Arrays;
import java.util.Scanner;

public class Main {
    private static int N=6010;
    private static int n,idx;
    private static int[] h=new int[N],e=new int[N],ne=new int[N];//邻接表存
    private static int[] happy=new int[N];//高兴度
    private static int[][] f=new int[N][2];//所有状态
    private static boolean[] has_fa=new boolean[N];//判断每个节点是否有根节点

    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        n=scanner.nextInt();
        for(int i=1;i<=n;i++)
            happy[i]=scanner.nextInt();
        Arrays.fill(h,-1);//表头初始化为-1
        for(int i=0;i<n-1;i++){//读入每条边
            int a,b;
            a=scanner.nextInt();
            b=scanner.nextInt();
            has_fa[a]=true;//b是a的父节点,所以a就有父节点了
            add(b,a);
        }
        int root=1;
        while (has_fa[root])//如果有父节点,看下一个点,直到没有父节点为止
            root++;
        dfs(root);
        //f[root][0]:不选根节点,f[root][1]:选择根节点
        System.out.println(Math.max(f[root][0],f[root][1]));

    }

    //邻接表插入一条边
    private static void add(int a, int b) {
        e[idx]=b;
        ne[idx]=h[a];
        h[a]=idx++;
    }

    //求每个状态
    private static void dfs(int u) {
        f[u][1]=happy[u];//选择这个点,需要加上高兴度
        for(int i=h[u];i!=-1;i=ne[i]){//再枚举所有儿子
            int j=e[i];//j表示u的某个儿子
            dfs(j);//先递归算
            f[u][0]+=Math.max(f[j][0],f[j][1]);
            f[u][1]+=f[j][0];
        }
    }
}



最短Hamilton路径

给定一张 n 个点的带权无向图,点从 0~n-1 标号,求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。

输入格式

第一行输入整数n。

接下来n行每行n个整数,其中第i行第j个整数表示点i到j的距离(记为a[i,j])。

对于任意的x,y,z,数据保证 a[x,x]=0,a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]>=a[x,z]。

输出格式

输出一个整数,表示最短Hamilton路径的长度。

数据范围

1≤n≤20
0≤a[i,j]≤107

输入样例:

5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0

输出样例:

18

样例

分析

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    private static int N=20,M=1<<N;
    private static int n;
    private static int[][] w=new int[N][N];//两点之间的距离
    private static int[][] f=new int[M][N];//状态

    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        n=scanner.nextInt();
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++)
                w[i][j]=scanner.nextInt();
        }

        //初始状态在0号点,从0走到0,走过的所有点只有0点,也就是第0位上是1,其余所有位是0
        for(int i=0;i<(1<<n);i++){//其余点
            Arrays.fill(f[i],Integer.MAX_VALUE/2);
        }
        f[1][0]=0;//起点
        //i,k代表所有的状态
        for(int i=0;i<(1<<n);i++){
            for(int j=0;j<n;j++){
                if((i>>j & 1)==1)//如果从0走到j的话一定需要包含j,i>>k & 1一定要是1才有意义
                    for(int k=0;k<n;k++)
                        if( ( (i-(1<<j)) >>k & 1)==1 )//如果从k这个点转移过来,i除去j这点之后,一定得包含k这个点,一定是1
                            f[i][j]=Math.min(f[i][j],f[i-(1<<j)][k]+w[k][j]);
            }

        }
        System.out.println(f[(1<<n)-1][n-1]);
    }
}


活动打卡代码 AcWing 91. 最短Hamilton路径

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    private static int N=20,M=1<<N;
    private static int n;
    private static int[][] w=new int[N][N];//两点之间的距离
    private static int[][] f=new int[M][N];//状态

    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        n=scanner.nextInt();
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++)
                w[i][j]=scanner.nextInt();
        }

        //初始状态在0号点,从0走到0,走过的所有点只有0点,也就是第0位上是1,其余所有位是0
        for(int i=0;i<(1<<n);i++){//其余点
            Arrays.fill(f[i],Integer.MAX_VALUE/2);
        }
        f[1][0]=0;//起点
        //i,k代表所有的状态
        for(int i=0;i<(1<<n);i++){
            for(int j=0;j<n;j++){
                if((i>>j & 1)==1)//如果从0走到j的话一定需要包含j,i>>k & 1一定要是1才有意义
                    for(int k=0;k<n;k++)
                        if( ( (i-(1<<j)) >>k & 1)==1 )//如果从k这个点转移过来,i除去j这点之后,一定得包含k这个点,一定是1
                            f[i][j]=Math.min(f[i][j],f[i-(1<<j)][k]+w[k][j]);
            }

        }
        System.out.println(f[(1<<n)-1][n-1]);
    }
}