最省納智捷1年新車83萬起工程師靠存股年領百萬股息吉隆坡最便宜行程一覽表晚會結束續攤大腸花 學...
2012-06-18 19:08:47 人氣(267) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][DP, JAVA] 11375 - Matches

0
收藏
0
推薦

Problem E: Matches

We can make digits with matches as shown below:

Given N matches, find the number of different numbers representable using the matches. We shall only make numbers greater than or equal to 0, so no negative signs should be used. For instance, if you have 3 matches, then you can only make the numbers 1 or 7. If you have 4 matches, then you can make the numbers 1, 4, 7 or 11. Note that leading zeros are not allowed (e.g. 001, 042, etc. are illegal). Numbers such as 0, 20, 101 etc. are permitted, though.

Input

Input contains no more than 100 lines. Each line contains one integer N (1 ≤ N ≤ 2000).

Output

For each N, output the number of different (non-negative) numbers representable if you have N matches.

Sample Input

3
4

Sample Output

2
4


一直被初始化搞死, 複習下 DP

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
BigInteger[] dp = new BigInteger[2001];
int[] m = {6,2,5,5,4,5,6,3,7,6};
for(int i = 1; i <= 2000; i++) {
dp[i] = BigInteger.valueOf(0);
}
for(int i = 1; i < 10; i++) {
dp[m[i]] = dp[m[i]].add(BigInteger.valueOf(1));
}
for(int i = 1; i <= 2000; i++) {
for(int j = 0; j < 10; j++) {
if(i-m[j] >= 1)
dp[i] = dp[i].add(dp[i-m[j]]);
}
}
dp[6] = dp[6].add(BigInteger.valueOf(1));
for(int i = 2; i <= 2000; i++) {
dp[i] = dp[i].add(dp[i-1]);
}
Scanner cin = new Scanner(System.in);
int n;
while(cin.hasNextInt()) {
n = cin.nextInt();
System.out.println(dp[n].toString());
}
}
}

11375Matches
台長:Morris
人氣(267) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][矩陣 D&C] 12470 - Tribonacci
此分類上一篇:[UVA][模數] 12465 - The Turanga Leela Problem

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文