蓝桥杯 算法提高 拿糖果(java)

时间:2022-01-18 11:09:56

蓝桥杯 算法提高 拿糖果(java)

按照样例输入,起始的糖果数为15,在小B第一次拿走1颗糖后,妈妈同样会拿走1颗糖,问题

就会变成在起始只有13颗糖的情况下最多能拿到多少颗糖;若小B又拿走1颗糖,妈妈又会拿走1颗,

问题又变成了在11颗中最多能拿到多少颗糖……很明显子问题新产生的问题并不是相互独立的,

应通过动态规划解题 :

通过题目写出状态转移方程: dp[i] = max{ dp[i] , dp[ i –temp * 2 ] + temp };

dp[i]  表示在糖果为i个时,小B能获取的最多糖果的个数.

temp  表示在糖果为i个时,小B和妈妈所能拿的糖果的个数.

写出状态转移方程后用代码实现,问题就解决了,具体代码如下:
import java.util.Scanner;
import java.util.Vector;

public class Main{

	static int[] dp = new int[100001];

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();

		//动态转换方程的实现
		for( int i=0; i<=n; i++ ){
			Vector<Integer> vec = f( i );
			int len = vec.size();
			for( int j=0; j<len; j++ ){
				dp[i] = Math.max( dp[i], dp[i-2*vec.get(j)]+vec.get(j) );
			}
		} 
		System.out.println(dp[n]);
	}

	//获取不大于根号下 num 的所有质因数,并用集合 Vector 储存 
	public static Vector<Integer> f( int num ){
		Vector<Integer> vec = new Vector<Integer>();
		for( int i=2; i * i<=num; i++ ){
			if( num % i == 0 ){
				vec.add(i);
			}
		}
		return vec;
	}
}