1
12
2013
7

TopCoder SRM 565

题目来自TopCoder

MonstersValley

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;
	}
};

DivisibleSequence

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=22*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);
}

这里出现了modular divisionModular multiplicative inverse(模反元素)的概念 和 费马小定理(Fermat's little theorem)

如果a-1和x对于m是同模的,则x就是a的模反元素,这时有a*x mod m = a*a-1 mod m = 1

模反元素可以用于计算modular division,p/q mod m 可以表示为 p*q-1 mod m,其中q-1是q的模反元素。

而费马小定理可以方便地解决m为素数时求解q-1的问题:

假如a是一个整数,p是一个质数,这个定理表明amod p = a mod p

如果a不是p的倍数,这个定理可以写成ap-1mod p = 1。

如此以来,对于本题我们只要计算ap-2即为a的模反元素。


怎样计算xy :

观察官方题解的modPow函数,这个方法巧妙地用o(log(y))的时间计算了x

代码维护了底数a和结果r。初始时r=1,a=x,每一步迭代中如果y是奇数,则r更新为r*a。然后底数a更新为a2,指数y更新为y/2。

这是因为xy=(x2)y/2*xy%2 ,这样计算xy就转化为计算(x2)y/2

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com