分类: C/C++
2008-03-30 09:44:00
经过了一段时间的努力,我再Pku上也算是有了一个阶段性的总结拉,下面是我就这段时间搞ACM来的一些代码的总结,具体的一些题目类型的总结看本Blog的相关文章。
huicpc26 ACM_PKU 代码总结
1、DP(动态规划)
/*1080-HumanGeneFunctions.cpp*/
观察题目给出的一个最优解:
AGTGATG
-GTTA-G
将其从某一处切开,如果左边部分的分值不是最大,那么将其进行调整,使其分值变大,
则整个解分值变大,与已知的最优矛盾。所以左边部分的分值必是最大。
同理,右边也是。可见满足最优子结构的性质。考虑使用DP:
设两个DNA序列分别为s1,s2,长度分别为len1,len2,score为分值表。
f[i,j]表示子串s1[1..i]和s2[1..j]的分值。考虑一个f[i,j],我们有:
1.s1取第i个字母,s2取“-”:f[i-1,j] + score[s1[i],''-'']
2.s1取“-”,s2取第j个字母:f[i,j-1] + score[''-'',s2[j]]
3.s1取第i个字母,s2取第j个字母:f[i-1,j-1] + score[s1[i],s2[j]]
即f[i,j] = max(f[i-1,j] + score[s1[i],''-''], f[i,j-1] + score[''-'',s2[j]], f[i-1,j-1] + score[s1[i],s2[j]]);
然后考虑边界条件,这道题为i或j为0的情况。
当i=j=0时,即为f[0,0],这是在计算f[1,1]时用到的,根据f[1,1] = f[0,0] + score[s1[i], s2[j]],明显有f[0,0] = 0。
当i=0时,即为f[0,1..len2],有了f[0,0],可以用f[0,j] = f[0,j-1] + table[''-'',s2[j]]来计算。
当j=0时,即为f[1..len1,0],有了f[0,0],可以用f[i,0] = f[i-1,0] + table[s1[i],''-'']来计算。
至于计算顺序,只要保证计算f[i,j]的时候,使用到的f[i-1,j],f[i,j-1],f[i-1,j-1]都计算出来了就行了。
所谓划分阶段也就是为了达到这个目的。这样我们使用一个二重循环就可以了。*/
#include
#include
#include
using namespace std;
#define MAX(a,b,c) (a>b?a:b)>c?(a>b?a:b):c
int ctoi(char a){
int b;
if(a==''A'') b = 0;
if(a==''C'') b = 1;
if(a==''G'') b = 2;
if(a==''T'') b = 3;
if(a==''-'') b = 4;
return b;
}
int main()
{
int t,j,k,m,n;
int f1,f2,f3;
int f[101][101];
int arr[5][5]={{5,-1,-2,-1,-3},{-1,5,-3,-2,-4},{-2,-3,5,-2,-2},{-1,-2,-2,5,-1},{-3,-4,-2,-1,0}};
string a,b;
cin>>t;
while(t--){
j = k = 0;
memset(f,0,sizeof(f));
cin>>m>>a;
cin>>n>>b;
for(j=0;j<=m;j++)
{
for(k=0;k<=n;k++)
{
if(j == 0 && k == 0)
{
f[j][k] = 0;
}
else if(j==0)
{
f[j][k] = f[j][k-1] + arr[ctoi(''-'')][ctoi(b[k-1])];
}
else if(k==0)
{
f[j][k] = f[j-1][k] + arr[ctoi(a[j-1])][ctoi(''-'')];
}
else
{
f1 = f[j-1][k] + arr[ctoi(a[j-1])][ctoi( ''-'')];
f2 = f[j][k-1] + arr[ctoi( ''-'')][ctoi(b[k-1])];
f3 = f[j-1][k-1] + arr[ctoi(a[j-1])][ctoi(b[k-1])];
f[j][k] = MAX(f1,f2,f3);
}
}
}
cout<<
}
return 0;
}
2、/*1088-滑雪.cpp*/
#include
using namespace std;
const int highest = 100000;
int high[100][100];
bool travel[100][100];
int value[100][100];
int r, c;
const int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
int find_rout(int x, int y){
int i, temp;
if(x < 0 || y < 0 || x >= r || y >= c)
return 0;
if(travel[x][y])
return value[x][y];
int max_rout = 1;
for(i = 0; i < 4; ++i){
if(high[x][y] > high[x + dir[i][0]][y + dir[i][1]])
{
temp = find_rout(x + dir[i][0], y + dir[i][1]);
if(max_rout < temp + 1)
max_rout = temp + 1;
}
}
travel[x][y] = true;
value[x][y] = max_rout;
return max_rout;
}
int main(){
cin >> r >> c;
int i, j;
int max_rout = 1;
for(i = 0; i < r; ++i)
for(j = 0; j < c; ++j){
travel[i][j] = false;
cin >> high[i][j];
}
for(i = 0; i < r; ++i)
for(j = 0; j < c; ++j) {
int temp = find_rout(i, j);
if(temp > max_rout)
max_rout = temp;
}
cout << max_rout << endl;
return 0;
}
3、精度运算
/*2262-Goldbach''sConjecture.cpp*/
#include
#include
void doRun(){
int i,j,sum,a;
long t;
while(cin>>a){
t = 0;
if(a== 0||a>10000)
break;
sum = 0;
i = 1;
while(1){
sum += i;
if(sum>=a){
t = a-(sum-i);
break;
}
i++;
}
t = t*i;
for(j=1;j
t += j*j;
}
cout<