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 阅读(925)
评论(0) 编辑 收藏 引用 所属分类:
算法题解