poj 1159 && poj 1836

两道简单的 dp题目

给一个字符串添加字符，使字符串变成回文串，很简单的一个dp，不过还是MLE了一次，改成了滚动数组就可以了

View Code

 1 const int N = 5010;
 2 int dp[2][N];
 3 char str[N];
 4 int main()
 5 {
 6     int i,j,n;
 7     //freopen("data.txt","r",stdin);
 8     while(scanf("%d",&n) != EOF)
 9     {
10         getchar();
11         scanf("%s",str + 1);
12         _clr(dp,0);
13         for(i = n; i >= 0; i--)
14         {
15             for(j = i; j <= n; j++)
16             {
17                 if(str[i] == str[j]) dp[i % 2][j] = dp[(i + 1) % 2][j - 1];
18                 else
19                 {
20                     dp[i % 2][j] = Min(dp[(i + 1) % 2][j],dp[i % 2][j - 1]);
21                     dp[i % 2][j] ++;
22                 }
23             }
24         }
25         printf("%d\n",dp[1][n]);
26     }
27     return 0;
28 }

题目：http://poj.org/problem?id=1836

给出 n 个人，求出队最少的人数，使得剩余的人都可以看到左无穷远或右无穷远，感觉很典型的一个dp求最长上升子序列的题目，不知道怎么pku题目列表里就把这个题归为了计算几何

枚举每一个点，正序求一遍最长上升子序列，倒序再求一遍，然后 ans = max ( lenu[ 1 ~~ i] + lend[ i + 1 ~~~~n])

View Code

 1 typedef long long ll;
 2 const int N = 1010;
 3 double p[N];
 4 int lenu[N],lend[N];
 5 bool v[N];
 6 int main()
 7 {
 8     int i,j;
 9     int n;
10     //freopen("data.txt","r",stdin);
11     while(scanf("%d",&n) != EOF)
12     {
13         _clr(lenu,0);
14         _clr(lend,0);
15         for(i = 1; i <= n; i++)
16         scanf("%lf",&p[i]);
17         lenu[1] = 1;   // 正序求
18         for(i = 2; i <= n; i++)
19         {
20             lenu[i] = 1;
21             int tlen = 0;
22             for(j = 1; j < i; j++)
23             if(p[i] > p[j])
24             if(tlen < lenu[j]) tlen = lenu[j];
25             lenu[i] = tlen + 1;
26         }
27         lend[n] = 1;  // 倒序求
28         for(i = n - 1; i >= 1; i--)
29         {
30             lend[i] = 1;
31             int tlen = 0;
32             for(j = n; j > i; j--)
33             if(p[i] > p[j])
34             if(tlen < lend[j]) tlen = lend[j];
35             lend[i] = tlen + 1;
36         }
37         int maxx = -1;  // 求和
38         for(i = 1; i <= n; i++)
39         {
40             for(j = i + 1; j <= n; j++)
41             maxx = Max(maxx,lenu[i] + lend[j]);
42         }
43         printf("%d\n",n - maxx);
44     }
45     return 0;
46 }