Climber.pI的OI之路

Through the darkest dark，may we see the light.

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 阅读(378) 评论(0)  编辑 收藏 引用 所属分类: 动态规划


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理