日本免费一区二区久久人人澡 ,人妻少妇精品久久,无码人妻精品一区二区三区久久久

NOIP 2004 合唱隊型

雙向最長上升子序列，枚舉k(0<=k<=n)，f[i] = max{f[j]}+1;
在tyvj提交一直RTE，原因未知.

1#include<stdio.h>
2#include<iostream>
3using namespace std;
4
5int main()
6{
7    FILE *fin, *fout;
8    fin = fopen("chorus.in", "r");
9    fout = fopen("chorus.out", "w");
10    int i, j, k, n, T[120] = {0}, f[120] = {0}, ans = 0, final = 0;
11    fscanf(fin, "%d", &n);
12    for (i = 1; i <= n; i++) fscanf(fin, "%d", &T[i]);
13    for (k = 1; k <= n; k++)
14    {
15        for (i = 1; i <= n; i++) f[i] = 1;
16        for (i = 1; i <= k; i++)
17            for (j = 1; j < i; j++)
18                if (T[j] < T[i] && f[j]+1 > f[i]) f[i] = f[j]+1;
19        ans = f[k]-1;
20        for (i = 1; i <= n; i++) f[i] = 1;
21        for (i = n; i >= k; i--)
22            for (j = n; j > i; j--)
23                if (T[j] < T[i] && f[j]+1 > f[i]) f[i] = f[j]+1;
24        ans += f[k];
25        if (ans > final) final = ans;
26    }
27    fprintf(fout, "%d\n", n-final);
28}
29

posted on 2010-09-20 21:35 Climber.pI 閱讀(394) 評論(0) 編輯收藏引用所屬分類: 動態(tài)規(guī)劃

只有注冊用戶登錄后才能發(fā)表評論。
【推薦】100%開源！大型工業(yè)跨平臺軟件C++源碼提供，建模，組態(tài)！

相關文章: Problem List (7.26 ~ 8.5) Problem List (7.13 ~ 7.20) Problem List (5.7) USACO 4.1.1 Nuggets NOIp 2005 過河 NOIp 2003 加分二叉樹 NOIp 2006 金明的預算方案 Dp札記 NOIp 2008 傳紙條 NOIp 2000 方格取數

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

Climber.pI的OI之路

NOIP 2004 合唱隊型

導航

統(tǒng)計信息

News

常用鏈接

留言簿

隨筆分類

隨筆檔案

My Blog

搜索

最新評論

閱讀排行榜

評論排行榜