[ACM] POJ 1205, 简单DP

12 Replies

DP就是每次在原序列右边加一个city的时候 (此时n个city) 只要看前一个状态 (n-1个city) 最右边的city的情况
也就是记录n个city时的三个状态 xxxV xxx> xxx<
xxxV 和 xxx< 的数量和就是要求的结果, xxx>是记录一下如果允许向右流水那么方案的数量
状态转移即为右图
然后dp[100]结果超过long long, 于是用BigInteger, 写这个报告的原因也是第一次用Java交OJ..

代码:
[java]

import java.math.*;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
BigInteger dp[][]=new BigInteger[101][2];
dp[1][0]=BigInteger.ONE;
dp[1][1]=BigInteger.ZERO;
for(int i=2;i<=100;i++) {
dp[i][0]=dp[i-1][0].add(dp[i-1][0]).add(dp[i-1][1]);
dp[i][1]=dp[i-1][0].add(dp[i-1][1]);
}
Scanner sc=new Scanner(System.in);
while(sc.hasNext()) {
int a=sc.nextInt();
System.out.println(dp[a][0].add(dp[a][1]));
}
}
}

[/java]

12 thoughts on “[ACM] POJ 1205, 简单DP”

Leave a Reply

Your email address will not be published. Required fields are marked *