//導(dǎo)彈，求最長(zhǎng)下降子序列長(zhǎng)度，注意輸出，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;
}
//標(biāo)準(zhǔn)LCS，把一個(gè)j寫成i導(dǎo)致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;
}
//害我沒睡好覺，靠，爛
#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;
}
//略
#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;
}
//黑書有介紹，參考，但要添加對(duì)相應(yīng)串的存儲(chǔ)，黑書的代碼有可改進(jìn)的...
#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;
}
#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;
}
#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;
}
#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;
}
摘要: 編寫將十字鏈表表示的矩陣A轉(zhuǎn)置的程序算法，轉(zhuǎn)置結(jié)果為另一個(gè)十字鏈表，并將該轉(zhuǎn)置矩陣以三元組(i，j，value)的形式輸出。
1#include<iostream> 2using namespace std; 3#define MAX 100 4 ...
閱讀全文
輸入二叉樹
先序，建樹，然后
中序線索化，遍歷輸出
1#include<iostream>
2using namespace std;
3
4enum PointerTag
5{
6 Link,Thread //枚舉值Link和Thread分別為0，1
7};
8
9struct BiThrNode //線索二叉樹的結(jié)點(diǎn)類型
10{
11 char data;
12 PointerTag LTag; //左標(biāo)志
13 PointerTag RTag; //右標(biāo)志
14 BiThrNode *lchild; //左孩子指針
15 BiThrNode *rchild; //右孩子指針
16};
17
18typedef BiThrNode* BiThrTree;
19BiThrNode *pre=NULL; //全局量
20
21void InOrderThreading(BiThrTree & Thrt,BiThrTree T);//線索化
22void InThreading(BiThrTree p);//中序遍歷線索化
23bool PreOrderCreatBiTree(BiThrTree &T);//先序建立樹
24void InOrderTraverse_Thr(BiThrTree T);//中序遍歷線索樹
25
26int main()
27{
28 BiThrTree T,Thrt;
29 printf("輸入先序序列('#'表示空節(jié)點(diǎn))建立二叉樹：\n");
30 PreOrderCreatBiTree(T);//先序建立樹
31 InOrderThreading(Thrt,T);//中序線索化
32 printf("中序線索化，中序遍歷得中綴式：\n");
33 InOrderTraverse_Thr(Thrt);//中序遍歷線索樹
34 printf("\n");
35 return 0;
36}
37
38void 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
55void 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
67bool PreOrderCreatBiTree(BiThrTree &T)
68{//該節(jié)點(diǎn)非空返回true，雙親節(jié)點(diǎn)對(duì)應(yīng)標(biāo)志Link，空時(shí)返回false，雙親節(jié)點(diǎn)對(duì)應(yīng)標(biāo)志應(yīng)為Thread
69 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; //左孩子存在則左標(biāo)志為L(zhǎng)ink
79 else T->LTag=Thread;
80 if(PreOrderCreatBiTree(T->rchild)) T->RTag=Link; //右孩子存在則右標(biāo)志為L(zhǎng)ink
81 else T->RTag=Thread;
82 }
83 return true;
84}
85
86
87void 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}