posts - 33,  comments - 33,  trackbacks - 0
Poj 2081
http://poj.org/problem?id=2081
求数列第i项 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9
解法:按照题目要求递推即可
#include <stdio.h>
#include 
<string.h>

bool visited[4000005];
int nums[4000005];

void pre()
{
    memset(visited,
0,sizeof(visited));
    memset(nums,
0,sizeof(nums));
    visited[
0= true;
    
for (int i = 1; i <= 500000++i)
    {
        
int k = nums[i-1- i;
        
if (k <=0 || visited[k])
        {
            nums[i] 
= nums[i-1+ i;
            visited[nums[i]] 
= true;
        }
        
else
        {
            nums[i] 
= nums[i-1- i;
            visited[nums[i]] 
= true;
        }
    }
}

int main()
{
    pre();
    
int n;
    
while(scanf("%d",&n) != EOF)
    {
        
if (n == -1)
        {
            
break;
        }
        printf(
"%d\n",nums[n]);
    }
    
return 0;
}

2250 
http://poj.org/problem?id=2250
最长公共串
  1 #include <iostream>
  2 #include <string.h>
  3 #include <string>
  4 #include <vector>
  5 using namespace std;
  6 
  7 string strs1[128];
  8 int len1;
  9 string strs2[128];
 10 int len2;
 11 int dp[128][128];
 12 int flags[128][128];//1 上 2 左 3 对角
 13 
 14 void Test()
 15 {
 16     memset(dp,0,sizeof(dp));
 17     memset(flags,0,sizeof(flags));
 18     for (int i = 1; i <= len1; ++i)
 19     {
 20         for (int j = 1; j <= len2; ++j)
 21         {
 22             if (strs1[i] == strs2[j])
 23             {
 24                 dp[i][j] = dp[i-1][j-1+ 1;
 25                 flags[i][j] = 3;
 26             }
 27             else
 28             {
 29                 int m1 = dp[i-1][j];
 30                 int m2 = dp[i][j-1];
 31                 if (m1 < m2)
 32                 {
 33                     dp[i][j] = m2;
 34                     flags[i][j] = 2;
 35                 }
 36                 else
 37                 {
 38                     dp[i][j] = m1;
 39                     flags[i][j] = 1;
 40                 }
 41             }
 42         }
 43     }
 44     int pos1 = len1;
 45     int pos2 = len2;
 46     vector<string> vec;
 47     while(true)
 48     {
 49         if (flags[pos1][pos2] == 3)
 50         {
 51             vec.push_back(strs1[pos1]);
 52             --pos1;
 53             --pos2;
 54         }
 55         else if (flags[pos1][pos2] == 2)
 56         {
 57             --pos2;
 58         }
 59         else if (flags[pos1][pos2] == 1)
 60         {
 61             --pos1;
 62         }
 63         else
 64             break;
 65     }
 66     for (int i =  vec.size()-1; i >=0 ; --i)
 67     {
 68         cout << vec[i];
 69         if (i == 0)
 70         {
 71             cout << endl;
 72         }
 73         else
 74         {
 75             cout << " ";
 76         }
 77     }
 78 }
 79 
 80 int main()
 81 {
 82     //freopen("data.txt","r",stdin);
 83     string input;
 84     int k = 0;
 85     len1 = len2 = 0;
 86     while(cin >> input)
 87     {
 88         if (input == "#")
 89         {
 90             if (k == 1)
 91             {
 92                 Test();
 93                 k = 0;
 94                 len1 = len2 = 0;
 95                 continue;
 96             }
 97             else
 98             {
 99                 k = 1;
100             }
101         }
102         if (k == 0)
103         {
104             strs1[++len1] = input;
105         }
106         else
107         {
108             strs2[++len2] = input;
109         }
110     }
111     return 0;
112 }



posted on 2012-03-26 20:19 bennycen 阅读(910) 评论(0)  编辑 收藏 引用 所属分类: 算法题解

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