wyiu - C++博客

pku 1887_DP

//导弹，求最长下降子序列长度，注意输出，1PE，o(╯□╰)o

#include<iostream>

using namespace std;

#define M 5000

int height[M+1];

int maxlen[M+1];

int dp(int n)

{

int i,j,tmp;

maxlen[0]=1;

for(i=1;i<n;i++)

{

tmp=0;

for(j=0;j<i;j++)

if(height[i]<height[j] && maxlen[j]>tmp)

tmp=maxlen[j];

maxlen[i]=tmp+1;

}

tmp=1;

for(i=0;i<n;i++)

if(maxlen[i]>tmp)

tmp=maxlen[i];

return tmp;

}

int main()

{

int k,n,t;

k=1;

n=0;

while(scanf("%d",&t)==1 )

{

if(t==-1 )

{

if(n==0) return 0;

else {

printf("Test #%d:\n maximum possible interceptions: %d\n\n",k,dp(n));

memset(height,0,sizeof(height));

memset(maxlen,0,sizeof(maxlen));

n=0;

k++;

}

} else height[n++]=t;

}

return 0;

}

posted @ 2009-05-23 18:35 wyiu 阅读(72) | 评论 (0) | 编辑收藏

pku 1458_DP

//标准LCS，把一个j写成i导致3RE，o(╯□╰)o

#include<iostream>

#include<string>

using namespace std;

#define M 800

char stra[M+1];

char strb[M+1];

int cs[M+1][M+1];

int m,n;

void LCS()

{

int i,j;

m=strlen(stra+1);

n=strlen(strb+1);

for(i=0;i<=m;i++)

cs[i][0]=0;

for(j=0;j<=n;j++)

cs[0][j]=0;

for(i=1;i<=m;i++)

for(j=1;j<=n;j++)

if(stra[i]==strb[j]) cs[i][j]=cs[i-1][j-1]+1;

else cs[i][j]=max(cs[i-1][j],cs[i][j-1]);

}

int main()

{

while(scanf(" %s %s",stra+1,strb+1)!=EOF)

{

LCS();

printf("%d\n",cs[m][n]);

}

return 0;

}

posted @ 2009-05-20 13:45 wyiu 阅读(89) | 评论 (0) | 编辑收藏

pku 1579_DP

//害我没睡好觉，靠，烂

#include<iostream>

using namespace std;

#define M 20

int res[M+1][M+1][M+1];

void dp()

{

int i,j,k;

for(i=0;i<=20;i++)

for(j=0;j<=20;j++)

res[i][j][0]=1;

for(j=0;j<=20;j++)

for(k=0;k<=20;k++)

res[0][j][k]=1;

for(i=0;i<=20;i++)

for(k=0;k<=20;k++)

res[i][0][k]=1;

for(i=1;i<=20;i++)

for(j=1;j<=20;j++)

for(k=1;k<=20;k++)

if(i<j && j<k)

res[i][j][k]=res[i][j][k-1]+res[i][j-1][k-1]-res[i][j-1][k];

else res[i][j][k]=res[i-1][j][k]+res[i-1][j-1][k]+res[i-1][j][k-1]-res[i-1][j-1][k-1];

}

int main()

{

int a,b,c;

dp();

while(scanf("%d%d%d",&a,&b,&c)==3 )

{

if(a==-1 && b==-1 && c==-1) return 0;

else {

if(a<=0 || b<=0 || c<=0)

printf("w(%d, %d, %d) = %d\n",a,b,c,1);

else {

if(a>20 || b>20 || c>20)

printf("w(%d, %d, %d) = %d\n",a,b,c,res[20][20][20]);

else printf("w(%d, %d, %d) = %d\n",a,b,c,res[a][b][c]);

}

return 0;

}

posted @ 2009-05-20 13:43 wyiu 阅读(78) | 评论 (0) | 编辑收藏

pku 1163_DP

//略

#include<iostream>

using namespace std;

int a[100][100];

int n;

int i,j;

void dp()

{

for(i=n-2;i>=0;i--)

for(j=0;j<=i;j++)

a[i][j]+=max(a[i+1][j],a[i+1][j+1]);

}

int main()

{

scanf("%d",&n);

for(i=0;i<n;i++)

for(j=0;j<=i;j++)

scanf("%d",&a[i][j]);

dp();

printf("%d\n",a[0][0]);

return 0;

}

posted @ 2009-05-19 01:20 wyiu 阅读(98) | 评论 (0) | 编辑收藏

pku 1141_DP

//黑书有介绍，参考，但要添加对相应串的存储，黑书的代码有可改进的...

#include<iostream>

#include<string>

using namespace std;

#define INF 2000000000

char str[102];

int d[102][102];

string ans[102][102];

void dp()

{

int i,j,k,p,n;

n=strlen(str+1);

for(i=1;i<=n;i++)

{

d[i][i-1]=0;

d[i][i]=1;

if(str[i]=='(') ans[i][i]="()";

if(str[i]==')') ans[i][i]="()";

if(str[i]=='[') ans[i][i]="[]";

if(str[i]==']') ans[i][i]="[]";

}

for(p=1;p<n;p++)

{

for(i=1;i<=n-p;i++)

{

j=i+p;

d[i][j]=INF;

if(str[i]=='(' && str[j]==')')

{

if(d[i+1][j-1]<d[i][j])

{

d[i][j]=d[i+1][j-1];

ans[i][j]='('+ans[i+1][j-1]+')';

}

else {

if(str[i]=='[' && str[j]==']')

{

if(d[i+1][j-1]<d[i][j])

{

d[i][j]=d[i+1][j-1];

ans[i][j]='['+ans[i+1][j-1]+']';

}

for(k=i;k<=j-1;k++)

{

if(d[i][k]+d[k+1][j]<d[i][j])

{

d[i][j]=d[i][k]+d[k+1][j];

ans[i][j]=ans[i][k]+ans[k+1][j];

}

cout<<ans[1][n]<<endl;

}

int main()

{

scanf("%s",str+1);

dp();

return 0;

}

posted @ 2009-05-19 01:00 wyiu 阅读(284) | 评论 (0) | 编辑收藏

全主元高斯消元法

#include<iostream>

#include<math.h>

using namespace std;

#define MAX 100

double A[MAX+1][MAX+1];

double B[MAX+1];

double X[MAX+1];

double Z[MAX+1];

int D[MAX+1]; //未知变量位置的变化

int n;

int e;

void input()

{

int i,j;

printf("n:");

scanf("%d",&n);

printf("A[][]:\n");

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

scanf("%lf",&A[i][j]);

printf("B[]:\n");

for(i=1;i<=n;i++)

scanf("%lf",&B[i]);

printf("e:");

scanf("%lf",&e);

}

void SwapE(double a,double b) //swap elements

{

double T;

T=a;

a=b;

b=T;

}

void SwapR(int k,int kmi)

{

int j;

for(j=k;j<=n;j++)

SwapE(A[k][j],A[kmi][j]);

}

void SwapC(int k,int kmj)

{

int i;

for(i=k;i<=n;i++)

SwapE(A[i][k],A[i][kmj]);

}

void AllGaussianElimination()

{

int kmi,kmj;//the i and j of the max(abs) element when k

int i,j,k;

double T;

for(i=1;i<=n;i++)//初始化位置变量位置

D[i]=i;

for(k=1;k<=n-1;k++)

{

//选主元

T=0;

for(i=k;i<=n;i++)

for(j=k;j<=n;j++)

if(fabs(A[i][j])>T) { T=fabs(A[i][j]); kmi=i;kmj=j;}

if(T<=e) {printf("Error!\n"); return ;}

if(kmi!=k) { SwapR(k,kmi); SwapE(B[k],B[kmi]); }

if(kmj!=k) { SwapC(k,kmj); SwapE(D[k],D[kmj]); }

//消元

for(i=k+1;i<=n;i++)

{

T=A[i][k]/A[k][k];

B[i]-=T*B[k];

for(j=k;j<=n;j++)

A[i][j]-=T*A[k][j];

}

//回代

if(A[n][n]<=e) {printf("Error!\n");return ;}

Z[n]=B[n]/A[n][n];

double S_Aij_Zj;

for(i=n-1;i>=1;i--)

{

S_Aij_Zj=0;

for(j=i+1;j<=n;j++)

S_Aij_Zj+=A[i][j]*Z[j];

Z[i]=(B[i]-S_Aij_Zj)/A[i][i];

}

for(j=1;j<=n;j++)

X[D[j]]=Z[j];

}

void print(double X[])

{

int i;

printf("X[]:\n");

for(i=1;i<=n;i++)

printf("%f\n",X[i]);

}

int main()

{

input();

AllGaussianElimination();

print(X);

system("pause");

return 0;

}

posted @ 2009-05-16 16:37 wyiu 阅读(801) | 评论 (0) | 编辑收藏

列主元高斯消元算法

#include<iostream>

#include<math.h>

using namespace std;

#define MAX 100

double A[MAX+1][MAX+1];

double B[MAX+1];

double X[MAX+1];

double e;

int n;

void ColGaussianElimination()

{

int i,j,k,kmi;

double T;

for(k=1;k<=n-1;k++)

{

//选主元

T=0;

for(i=k;i<=n;i++)

if( fabs(A[i][k])> T ){ T=A[i][k];kmi=i;}

if( T<=e) { printf("Error!\n"); return ;}

if(kmi!=k)

{

T=B[k];B[k]=B[kmi];B[kmi]=T; //swap B[k] and B[kmi]

for(j=k;j<=n;j++) //swap row kmi and k of A

{

T=A[k][j];

A[k][j]=A[kmi][j];

A[kmi][j]=T;

}

//消元

for(i=k+1;i<=n;i++)

{

T=A[i][k]/A[k][k];

B[i]-=T*B[k];

for(j=k;j<=n;j++)

A[i][j]-=T*A[k][j];

}

//回代

if( fabs(A[n][n])<=e ) { printf("Error!\n"); return ;}

X[n]=B[n]/A[n][n];

double S_Aij_Xj;

for(i=n-1;i>=1;i--)

{

S_Aij_Xj=0;

for(j=i+1;j<=n;j++)

S_Aij_Xj+=A[i][j]*X[j];

X[i]=(B[i]-S_Aij_Xj)/A[i][i];

}

void print(double X[])

{

int i;

printf("X[]:\n");

for(i=1;i<=n;i++)

printf("%f\n",X[i]);

}

int main()

{

int i,j;

printf("n:");

scanf("%d",&n);

printf("A[][]:\n");

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

scanf("%lf",&A[i][j]);

printf("B[]:\n");

for(i=1;i<=n;i++)

scanf("%lf",&B[i]);

printf("e:");

scanf("%lf",&e);

ColGaussianElimination();

print(X);

system("pause");

return 0;

}

posted @ 2009-05-16 16:34 wyiu 阅读(614) | 评论 (0) | 编辑收藏

顺序高斯消元算法

#include<iostream>

#include<math.h>

using namespace std;

#define MAX 100

double A[MAX+1][MAX+1];

double B[MAX+1];

double X[MAX+1];

double e;

int n;

void OrderGaussianElimination()

{

int i,j,k;

double T;

//消元

for(k=1;k<=n-1;k++)

{

if( fabs(A[k][k])<=e ) { printf("Error!\n"); return ;}

for(i=k+1;i<=n;i++)

{

T=A[i][k]/A[k][k];

B[i]-=T*B[k];

for(j=k;j<=n;j++)

A[i][j]-=T*A[k][j];

}

//回代

if( fabs(A[n][n])<=e ) { printf("Error!\n"); return ;}

X[n]=B[n]/A[n][n];

double S_Aij_Xj;

for(i=n-1;i>=1;i--)

{

S_Aij_Xj=0;

for(j=i+1;j<=n;j++)

S_Aij_Xj+=A[i][j]*X[j];

X[i]=(B[i]-S_Aij_Xj)/A[i][i];

}

void print(double X[])

{

int i;

printf("X[]:\n");

for(i=1;i<=n;i++)

printf("%f\n",X[i]);

}

int main()

{

int i,j;

printf("n:");

scanf("%d",&n);

printf("A[][]:\n");

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

scanf("%lf",&A[i][j]);

printf("B[]:\n");

for(i=1;i<=n;i++)

scanf("%lf",&B[i]);

printf("e:");

scanf("%lf",&e);

OrderGaussianElimination();

print(X);

return 0;

}

posted @ 2009-05-16 16:32 wyiu 阅读(232) | 评论 (0) | 编辑收藏

矩阵转置_十字链表

摘要: 编写将十字链表表示的矩阵A转置的程序算法，转置结果为另一个十字链表，并将该转置矩阵以三元组(i，j，value)的形式输出。 1#include<iostream> 2using namespace std; 3#define MAX 100 4 ... 阅读全文

posted @ 2009-05-13 17:06 wyiu 阅读(955) | 评论 (0) | 编辑收藏

二叉树线索化

输入二叉树先序，建树，然后中序线索化，遍历输出

#include<iostream>
2

using namespace std;
3

enum PointerTag
5

{
6

Link,Thread //枚举值Link和Thread分别为0，1
7

};
8

struct BiThrNode //线索二叉树的结点类型
10

{
11

char data;
12

PointerTag LTag; //左标志
13

PointerTag RTag; //右标志
14

BiThrNode *lchild; //左孩子指针
15

BiThrNode *rchild; //右孩子指针
16

};
17

typedef BiThrNode* BiThrTree;
19

BiThrNode *pre=NULL; //全局量
20

void InOrderThreading(BiThrTree & Thrt,BiThrTree T);//线索化
22

void InThreading(BiThrTree p);//中序遍历线索化
23

bool PreOrderCreatBiTree(BiThrTree &T);//先序建立树
24

void InOrderTraverse_Thr(BiThrTree T);//中序遍历线索树
25

int main()
27

{
28

BiThrTree T,Thrt;
29

printf("输入先序序列('#'表示空节点)建立二叉树：\n");
30

PreOrderCreatBiTree(T);//先序建立树
31

InOrderThreading(Thrt,T);//中序线索化
32

printf("中序线索化，中序遍历得中缀式：\n");
33

InOrderTraverse_Thr(Thrt);//中序遍历线索树
34

printf("\n");
35

return 0;
36

}
37

void InOrderThreading(BiThrTree & Thrt,BiThrTree T)
39

{
40

Thrt=new BiThrNode;
41

Thrt->LTag=Link;
42

Thrt->RTag=Thread;
43

Thrt->rchild=Thrt;
44

if(!T) Thrt->lchild=Thrt;
45

else{
46

Thrt->lchild=T;
47

pre=Thrt;
48

InThreading(T);
49

pre->rchild=Thrt;
50

pre->RTag=Thread;
51

Thrt->rchild=pre;
52

}
53

}
54

void InThreading(BiThrTree p)
56

{
57

if(p)
58

{
59

InThreading(p->lchild);
60

if(!p->lchild){ p->LTag=Thread; p->lchild=pre;}
61

if(!pre->rchild){ pre->RTag=Thread; pre->rchild=p; }
62

pre=p;
63

InThreading(p->rchild);
64

}
65

}
66

bool PreOrderCreatBiTree(BiThrTree &T)
68

{//该节点非空返回true，双亲节点对应标志Link，空时返回false，双亲节点对应标志应为Thread

char ch;
70

scanf("%c",&ch);
71

if(ch=='#')
72

{
73

T=NULL;
74

return false;
75

}else {
76

T=new BiThrNode;
77

T->data=ch;
78

if(PreOrderCreatBiTree(T->lchild)) T->LTag=Link; //左孩子存在则左标志为Link
79

else T->LTag=Thread;
80

if(PreOrderCreatBiTree(T->rchild)) T->RTag=Link; //右孩子存在则右标志为Link
81

else T->RTag=Thread;
82

}
83

return true;
84

}
85

void InOrderTraverse_Thr(BiThrTree T)
88

{
89

BiThrNode *p;
90

p=T->lchild;
91

while(p!=T)
92

{
93

while(p->LTag==Link) p=p->lchild;
94

printf("%c",p->data);
95

while(p->RTag==Thread && p->rchild!=T) //if(p->RTag==Thread && p->rchild!=T)
96

{
97

p=p->rchild;
98

printf("%c",p->data);
99

}
100

p=p->rchild;
101

}
102

}

posted @ 2009-05-13 17:00 wyiu 阅读(623) | 评论 (0) | 编辑收藏

仅列出标题

常用链接

留言簿(1)

随笔分类(84)

随笔档案(100)

向高手学习

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜