Baudelaire is Programmer

Problem Statement:  

Manao is traversing a valley inhabited by monsters. During his journey, he will encounter several monsters one by one. The scariness of each monster is a positive integer. Some monsters may be scarier than others. The i-th (0-based index) monster Manao will meet has scariness equal to dread[i].  Manao is not going to fight the monsters. Instead, he will bribe some of them and make them join him. To bribe the i-th monster, Manao needs price[i] gold coins. The monsters are not too greedy, therefore each value in price will be either 1 or 2.  At the beginning, Manao travels alone. Each time he meets a monster, he first has the option to bribe it, and then the monster may decide to attack him. A monster will attack Manao if and only if he did not bribe it and its scariness is strictly greater than the total scariness of all monsters in Manao's party. In other words, whenever Manao encounters a monster that would attack him, he has to bribe it. If he encounters a monster that would not attack him, he may either bribe it, or simply walk past the monster

You are given the vector <int>s dread and price. Compute the minimum price Manao will pay to safely pass the valley.

 

用dp[p][n]表示Manao用p个金币通过前n个monsters可以获得的最大scariness值，则有

dp[n][p]=max{dp[n-1][p](dp[n-1][p]>scariness[n]), dp[n-1][p-price[n]]+scariness[n]}

如果用p个金币不能通过前n个monsters那么dp[n][p]=-1

#include<vector>
#include<iostream>
using namespace std;
class MonstersValley2{
	public:
	int minimumPrice(vector <int> dread,vector <int> price){
		long long dp[21][41];
		for(int i=0;i<=40;i++)dp[0][i]=0;
		for(int i=1;i<=dread.size();i++){
			for(int j=0;j<=40;j++){
				dp[i][j]=-1;
				if(dp[i-1][j]>=dread[i-1])dp[i][j]=dp[i-1][j];
				if(j>=price[i-1]&&dp[i-1][j-price[i-1]]!=-1){
					long long t=dp[i-1][j-price[i-1]]+dread[i-1];
					if(t>dp[i][j])dp[i][j]=t;
				}
				cout<<dp[i][j]<<' ';
			}
			cout<<endl;
		}
		for(int j=0;j<=40;j++){
			if(dp[dread.size()][j]!=-1)return j;
		}
		return -1;
	}
};

Problem Statement:

A divisible sequence with starting value N and length H is a sequence of positive integers with the following properties:

The sequence has H elements, labeled A[0] through A[H-1].

A[0] equals N.

For each i between 0 and H-2, inclusive, A[i+1] divides A[i].

You are given the ints N and H. Let C be the count of all divisible sequences with starting value N and length H. Return the value (C modulo 1,000,000,009).

 

首先对N进行因数分解，比如12=2²*3

这样一步步生成下一个元素的过程中，只要各个因子对应的指数不增，则最终形成一个Divisible Sequence。

注意到各个因子的指数变化是相互独立的，所以这个问题就转化为求一个以正整数开头的单调不增序列的个数。

比如12的例子，因子2对应的指数为2，生成下一个元素的过程中指数2或者不变，或者减小。

---

生成单调序列的方法：

设序列头元素为整数x(x>0)，要生成长度为H的单调不增序列。

这个过程可以表示为x次减1操作和H-1次取数操作的组合。

如x=2，H=3的情况下，操作序列：减1、取数、减1、取数、取数 形成一个单调不增序列1,0,0

所以这样的序列共有C(H-1+c,c)个。

 

这样一来整个算法流程可以概括为：

1.因数分解，提取各个质因数的指数

2.计算各自的单调序列个数

3.以上单调序列的个数相乘得到答案

---

质因数分解的试除法：

官方题解提供的代码

    // Let us use trial divison to find prime factors p
    for (int p=2; p <= N/p; p++) {
        int c = 0;
        while (N % p == 0) {
            N /= p;	
            c++;
        }
        res = ( res * C(H-1+c, c) ) % MOD;
    }
    if (N > 1) {
        // N is one last prime factor, c = 1
        // C(H-1+1,1) = H
        res = ( res * H ) % MOD;
    }

注意大于sqrt(N)的质因子最多只有一个，所以最后只要检测N是否大于1，如果大于1的话N就是最后的质因数。

---

计算C(n,k)的方法：

官方题解提供的代码

final int MOD = 1000000009;
// Calculates x raised to the y-th power modulo MOD
long modPow(long x, long y)
{
    long r=1, a=x;
    while (y > 0) {
        if ( (y&1)==1 ) {
            r = (r * a) % MOD;
        }
        a = (a * a) % MOD;
        y /= 2;
    }
    return r;
}
// Modular multiplicative inverse through Fermat's little theorem:
long modInverse(long x)
{
    return modPow(x, MOD-2);
}
// Modular division x / y, find modular multiplicative inverse of y
// and multiply by x.
long modDivision(long p, long q)
{
    return (p * modInverse(q)) % MOD;
}
// Binomial coifficient C(n,k) in O(k) time.
long C(long n, int k)
{
    if (k > n) {
        return 0;
    }
    long p = 1, q = 1;
    for (int i=1; i<=k; i++) {
        q = ( q * i) % MOD;
        p = ( p * (n - i + 1) ) % MOD;
    }
    return modDivision( p, q);
}