青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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 ，嘻嘻

 1import java.io.*;
 2import java.math.*;
 3public class Main {
 4
 5    /** *//**
 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
24    
25
26}
27

posted on 2011-01-15 17:22 yzhw 閱讀(229) 評論(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

網站導航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理

Powered by:
C++博客
Copyright © yzhw

導航

• 首頁
• 新隨筆
• 聯系
• 管理

統計

• 隨筆 - 183
• 文章 - 2
• 評論 - 27
• 引用 - 0

公告

留言簿(1)

• 給我留言
• 查看公開留言
• 查看私人留言

隨筆分類(227)

• combination math(7) (rss)
• data struct(48) (rss)
• DP(46) (rss)
• geometry&phycise(13) (rss)
• graph(47) (rss)
• numberic(8) (rss)
• others(5) (rss)
• search(23) (rss)
• simple problem~(15) (rss)
• string algorithm(11) (rss)
• ujs acm training(4) (rss)

文章分類(2)

• combination math (rss)
• data struct (rss)
• DP (rss)
• graph theory(1) (rss)
• numberic (rss)
• others(1) (rss)
• search (rss)

OJ

• lunzi
• whu fatboy_cw
• yzu大牛

最新隨筆

搜索

積分與排名

• 積分 - 57250
• 排名 - 406

最新評論

閱讀排行榜