练习Day——9

K好数

（存疑）
题目描述
如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4，L = 2的时候，所有K好数为11、13、20、22、30、31、33 共7个。由于这个数目很大，请你输出它对1000000007取模后的值。

输入
输入包含两个正整数，K和L。

输出
输出一个整数，表示答案对1000000007取模后的值。

样例输入
4 2

样例输出
7

package 前170题;

import java.util.Scanner;

//K好数
public class ALGO_3 {
    public static int mod = 1000000007;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int k= scan.nextInt();
        int l =scan.nextInt();
        int[][] num = new int[101][101];//num[i][j]表示L位K进制数中第i位数大小为j，这样的数有几个
        
        fun(num,k, l);
        scan.close();
    }
    public static void fun(int num[][],int k,int l){
        for (int i = 0; i < k; i++) {
            num[1][i] = 1;//目标数最低位依次初始化为0~k-1,且每一个数只出现一次
        }
        
        for(int i=2;i<=l;i++){//依次确定第2、3、4.....l位的数字
            for (int j = 0; j < k; j++) {
                for (int m = 0; m < k; m++) {
                    if(m-1!=j && m+1!=j){//两位数字不相邻
                        num[i][j]+=num[i-1][m];
                        num[i][j]%=mod;
                    }
                }
            }
        }
        int sum=0;
        for (int i = 1; i < k; i++) {//除去最高位为0的情况
            sum+=num[l][i];
            sum%=mod;
        }
        System.out.println(sum);
    }
}

结点选择

（存很大疑！！这个代码是参考的百度文库一篇答案：https://wenku.baidu.com/view/421185eba6c30c2259019efd.html?fr=search-4。但是我只搞懂了50%，最终得分也只有50%，真是令菜鸡头秃。）
题目描述
有一棵 n 个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少？

输入
第一行包含一个整数 n 。
接下来的一行包含 n 个正整数，第 i 个正整数代表点 i 的权值。
接下来一共 n-1 行，每行描述树上的一条边。

输出
输出一个整数，代表选出的点的权值和的最大值。

样例输入
5
1 2 3 4 5
1 2
1 3
2 4
2 5

样例输出
12

样例说明
选择3、4、5号点，权值和为 3+4+5 = 12 。

数据规模与约定
对于20%的数据， n <= 20。
对于50%的数据， n <= 1000。
对于100%的数据， n <= 100000。
权值均为不超过1000的正整数。

import java.io.*;
import java.util.*;

public class Main {
	final static int MAXN=10001;
	class Tree{
		int u,v,next;
		Tree(int U,int V,int N){
			u=U;
			v=V;
			next=N;
		}
	}
	int count;
	int dp[][]=new int[MAXN][2];
	Tree t[]=new Tree[MAXN*2];
	int head[]=new int[MAXN];
	int sta[]=new int[MAXN*2];
	boolean vis[]=new boolean[MAXN];
	
	void add(int u,int v) {
		t[count]=new Tree(u,v,head[u]);
		head[u]=count++;
	}
	
	void dfs(int x,int f) {
		Arrays.fill(vis, false);
		int top=0;
		vis[x]=true;
		sta[top++]=x;
		while(top>0) {
			int u=sta[top-1];
			boolean ed=false;
			for(int i=head[u];i+1!=0;i=t[i].next) {
				int v=t[i].v;
				if(vis[v])
					continue;
				ed=true;
				sta[top++]=v;
				vis[v]=true;
			}
			if(ed)
				continue;
			--top;
			for(int i=head[u];i+1!=0;i=t[i].next) {
				int v=t[i].v;
				dp[v][0]+=Math.max(dp[u][0], dp[u][1]);
				dp[v][1]+=dp[u][0];
			}
		}
	}
	
	void run() throws IOException {
		int n=cin.nextInt();
		for(int i=1;i<=n;i++) {
			dp[i][1]=cin.nextInt();
		}
		Arrays.fill(head, -1);
		
		for(int i=1;i<n;i++) {
			int u=cin.nextInt();
			int v=cin.nextInt();
			add(u,v);
			add(v,u);
		}
		
		dfs(1,-1);
		int res=Math.max(dp[1][0], dp[1][1]);
		out.println(res);
		out.close();
	}
    public static void main(String[] args) throws IOException{
    	new Main().run();
    }
    
    Main(){
    	cin=new InputReader(System.in);
    	out=new PrintWriter(System.out);
    }
    
    PrintWriter out;
    InputReader cin;
    
    class InputReader{
    	InputReader(InputStream in){
    		reader=new BufferedReader(new InputStreamReader(in));
    		tokenizer=new StringTokenizer("");
    	}
    	private String next()throws IOException{
    		while(!tokenizer.hasMoreTokens()) {
    			tokenizer=new StringTokenizer(reader.readLine());
    		}
    		return tokenizer.nextToken();
    	}
    	public Integer nextInt()throws IOException{
    		return Integer.parseInt(next());
    	}
    	private BufferedReader reader;
    	private StringTokenizer tokenizer;
    }
}
/*第一行包含一个整数 n 。

接下来的一行包含 n 个正整数，第 i 个正整数代表点 i 的权值。

接下来一共 n-1 行，每行描述树上的一条边。

输出格式
输出一个整数，代表选出的点的权值和的最大值。*/

本文地址：https://blog.csdn.net/qiankendeNMY/article/details/107825257