Algoogle

Algorithm for Programming Contest

PKU 3181 Dollar Dayz

Category: PKU Tag: big-integer, dp

Dollar Dayz

問題概要


解法


解法としてはDPで組み合わせを求めるだけだが, 数が大きくなるため多倍長整数型でやらなければならない.
しかもC++で下手な実装だと余裕でTLEする.
Java安定.

####


(PKU3181.java) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.math.BigInteger;
import java.util.Scanner;

public class POJ3181{

    void solve(){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(), K = sc.nextInt();
        BigInteger dp[][] = new BigInteger[K+1][N+1];
        for(int j = 0; j <= N; j++) dp[0][j] = new BigInteger("0");
        dp[0][0] = new BigInteger("1");
        for(int i = 1; i <= K; i++){
            for(int j = 0; j <= N; j++) dp[i][j] = new BigInteger("0");
            for(int k = 0; k <= N; k += i)
                for(int j = N; j >= k; j--)
                    dp[i][j] = dp[i][j].add(dp[i-1][j-k]);
        }
        System.out.println(dp[K][N]);
    }

    public static void main(String[] args){
        new POJ3181().solve();
    }
}

Comments