pku1205 Water Treatment Plants 递推（说DP也可以把。。）

题意：
一个污水处理系统吗，n个城市，每个城市可以选择
1、将左边城市过来的污水和右边城市过来的污水连同本身的污水排到河里
2、将左边来的污水连同自己的污水排到右边
3、将右边来的污水连同自己的污水排到左边

解法：
设状态dp[i][0]为第i个城市选择将污水传到左边的方案数，dp[i][1]为第i个城市选择将污水排入河道的方案数，dp[i][2]为选择将污水排到右边城市的方案数
然后有递推式
dp[i][2]=dp[i][1]=sum(dp[i-1][j]),j=0,1,2
dp[i][0]=dp[i-1][0]+dp[i-1][1]
这个应该不难理解吧？
如果最后一个城市选择后两种方案，那么前面城市怎么连都无所谓
而最后一个城市选择第一个方案，那么第n-1个城市不能选择将污水排到第n个城市
注意初始条件，dp[1][0]=0,dp[1][1]=dp[1][2]=1;
然后就是java BigInteger ，嘻嘻

import java.io.*;
2

import java.math.*;
3

public class Main {
4

/**
6

* @param args
7

*/
8

public static void main(String[] args) throws IOException{
9

StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
10

BigInteger dp[][]=new BigInteger[101][3];
11

dp[1][0]=BigInteger.ZERO;
12

dp[1][1]=BigInteger.ONE;
13

dp[1][2]=BigInteger.ONE;
14

for(int i=2;i<=100;i++)
15

{
16

dp[i][1]=dp[i-1][0].add(dp[i-1][1].add(dp[i-1][2]));
17

dp[i][0]=dp[i-1][0].add(dp[i-1][1]);
18

dp[i][2]=dp[i-1][0].add(dp[i-1][1].add(dp[i-1][2]));
19

}
20

while(in.nextToken()!=in.TT_EOF)
21

System.out.println(dp[(int)in.nval][0].add(dp[(int)in.nval][1]));
22

}
23

}
27

posted on 2011-01-15 17:22 yzhw 阅读(266) 评论(0) 编辑收藏引用所属分类: DP

只有注册用户登录后才能发表评论。


相关文章: pku3903 最长递增字串的单调性优化 pku 3998 Land Division DP斜率优化 The 36th ACM/ICPC Asia Regional Dalian Online Contest 大连2011ICPC网络赛个人题解 pku3124 The Bookcase 扩展背包好题 pku1202 Family DAG图上的概率DP pku 1946 Cow Cycling 非常好的DP pku1948 Triangular Pastures DP+枚举。海伦公式 pku1335 Digital Onion 递归 pku1332 Finding Liars DP 经典好题 pku1337 A Lazy Worker 很诡异的DP

网站导航: 博客园博客园最新博文博问管理

2012年2月

日

一

二

三

四

五

六

统计

随笔 - 183
文章 - 2
评论 - 27
引用 - 0

公告

统计系统

留言簿(1)

随笔分类(227)

文章分类(2)

OJ

搜索

积分与排名

积分 - 63765
排名 - 379