[动态规划] pku1080 二维DP
评论33次阅读2007.10.12 22:25; 作者：Felicia
很简单的DP，也是很基础的DP。做法就不说啦：）
下面是我的代码
下载: pku1080.cpp
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int n,i,j,k,la,lb;
char a[101],b[101];
int aa[101],bb[101];
int f[101][101];
int d[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};
main(){
scanf("%d",&n);
for (k=1;k<=n;k++){
scanf("%d%s",&la,a);
scanf("%d%s",&lb,b);
for (i=0;i<=la-1;i++)
if (a[i]=='A') aa[i+1]=0;
else if (a[i]=='C') aa[i+1]=1;
else if (a[i]=='G') aa[i+1]=2;
else if (a[i]=='T') aa[i+1]=3;
for (i=0;i<=lb-1;i++)
if (b[i]=='A') bb[i+1]=0;
else if (b[i]=='C') bb[i+1]=1;
else if (b[i]=='G') bb[i+1]=2;
else if (b[i]=='T') bb[i+1]=3;
for (i=0;i<=la;i++) for (j=0;j<=lb;j++) f[i][j]=-2147483647;
f[0][0]=0;
for (i=1;i<=lb;i++) f[0][i]=f[0][i-1]+d[bb[i]][4];
for (i=1;i<=la;i++) f[i][0]=f[i-1][0]+d[aa[i]][4];
for (i=0;i<=la;i++)
for (j=0;j<=lb;j++){
if (f[i][j]+d[aa[i+1]][4]>f[i+1][j]) f[i+1][j]=f[i][j]+d[aa[i+1]][4];
if (f[i][j]+d[bb[j+1]][4]>f[i][j+1]) f[i][j+1]=f[i][j]+d[bb[j+1]][4];
if (f[i][j]+d[aa[i+1]][bb[j+1]]>f[i+1][j+1]) f[i+1][j+1]=f[i][j]+d[aa[i+1]][bb[j+1]];
}
printf("%d\n",f[la][lb]);
}
}
#include <stdlib.h>
#include <string.h>
int n,i,j,k,la,lb;
char a[101],b[101];
int aa[101],bb[101];
int f[101][101];
int d[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};
main(){
scanf("%d",&n);
for (k=1;k<=n;k++){
scanf("%d%s",&la,a);
scanf("%d%s",&lb,b);
for (i=0;i<=la-1;i++)
if (a[i]=='A') aa[i+1]=0;
else if (a[i]=='C') aa[i+1]=1;
else if (a[i]=='G') aa[i+1]=2;
else if (a[i]=='T') aa[i+1]=3;
for (i=0;i<=lb-1;i++)
if (b[i]=='A') bb[i+1]=0;
else if (b[i]=='C') bb[i+1]=1;
else if (b[i]=='G') bb[i+1]=2;
else if (b[i]=='T') bb[i+1]=3;
for (i=0;i<=la;i++) for (j=0;j<=lb;j++) f[i][j]=-2147483647;
f[0][0]=0;
for (i=1;i<=lb;i++) f[0][i]=f[0][i-1]+d[bb[i]][4];
for (i=1;i<=la;i++) f[i][0]=f[i-1][0]+d[aa[i]][4];
for (i=0;i<=la;i++)
for (j=0;j<=lb;j++){
if (f[i][j]+d[aa[i+1]][4]>f[i+1][j]) f[i+1][j]=f[i][j]+d[aa[i+1]][4];
if (f[i][j]+d[bb[j+1]][4]>f[i][j+1]) f[i][j+1]=f[i][j]+d[bb[j+1]][4];
if (f[i][j]+d[aa[i+1]][bb[j+1]]>f[i+1][j+1]) f[i+1][j+1]=f[i][j]+d[aa[i+1]][bb[j+1]];
}
printf("%d\n",f[la][lb]);
}
}
发表回复
- 评论 (0)
- 引用通告 (0)
发表评论 引用通告暂无评论.
暂无引用通告