算法实验二。
问题 A: 最长公共子序列
题目描述
给你一个序列X和另一个序列Z，当Z中的所有元素都在X中存在，并且在X中的下标顺序是严格递增的，那么就把Z叫做X的子序列。
例如：Z=
现给你两个序列X和Y，请问它们的最长公共子序列的长度是多少？
输入
输入包含多组测试数据。每组输入占一行，为两个字符串，由若干个空格分隔。每个字符串的长度不超过100。
输出
对于每组输入，输出两个字符串的最长公共子序列的长度。
样例输入
abcfbc abfcab
programming contest
abcd mnp
样例输出
4
2
0
提示
代码
#include<bits/stdc++.h>
using namespace std;
/*void LCSlength(int m,int n,char *x,char *y,int c[105][105],int b[105][105])
{
int i,j;
for(i=1;i<=m;i++)
c[i][0]=0;
for(i=1;i<=n;i++)
c[0][i]=0;
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
if(x[i]==y[i])
{
c[i][j]=c[i-1][j-1]+1;
b[i][j]=1;
}
else if(c[i-1][j]>=c[i][j-1])
{
c[i][j]=c[i-1][j];
b[i][j]=2;
}
else
{
c[i][j]=c[i][j-1];
b[i][j]=3;
}
}
}
}
*/
int main()
{
char x[105],y[105];
int c[105][105];
while(cin>>x+1)
{
cin>>y+1;
int m=strlen(x+1);
int n=strlen(y+1);
for(int i=0;i<=m;i++)
c[0][i]=0;
for(int i=0;i<=n;i++)
c[i][0]=0;
/*for(int i=0;i<=105;i++)
{
for(int j=0;j<=105;j++)
{
c[i][j]=0;
b[i][j]=0;
}
}*/
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(x[i]==y[j])
c[i][j]=c[i-1][j-1]+1;
else
c[i][j]=max(c[i-1][j],c[i][j-1]);
}
}
//cout<<x+1<<y+1<<endl;
//cout<<m<<n<<endl;
cout<<c[m][n]<<endl;
}
return 0;
}
问题 B: 矩阵连乘
题目描述
给定n个矩阵{A1,A2,…,An}，及m个矩阵连乘的表达式，判断每个矩阵连乘表达式是否满足矩阵乘法法则，如果满足，则计算矩阵的最小连乘次数，如果不满足输出“MengMengDa“。
输入
输入数据由多组数据组成（不超过10组样例）。每组数据格式如下：
第一行是2个整数n (1≤n≤26)和m(1≤m≤3)，表示矩阵的个数。
接下来n行，每行有一个大写字母，表示矩阵的名字，后面有两个整数r和c，分别表示该矩阵的行数和列数，其中1<r, c<100。
第n+1行到第n+m行，每行是一个矩阵连乘的表达式(2<=矩阵个数<=100)。
输出
对于每个矩阵连乘表达式，如果运算不满足矩阵乘法法则的情况（即左矩阵列数与右矩阵的行数不同），则输出“MengMengDa”，否则输出最小矩阵连乘次数。
数据保证结果不超过1e9。
样例输入
3 2
A 10 100
B 5 50
C 100 5
ACB
ABC
样例输出
7500
MengMengDa
提示
代码
#include<iostream>
#include<string.h>
using namespace std;
int m[105][105]={0};
int p[200];
int maxchain(int n)
{
for(int i=1;i<=n;i++)
{
m[i][i]=0;
}
for(int r=2;r<=n;r++)
{
for(int i=1;i<=n-r+1;i++)
{
int j=i+r-1;
m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
for(int k=i+1;k<j;k++)
{
int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
if(t<m[i][j])
{
m[i][j]=t;
}
}
}
}
return m[1][n];
}
int main()
{
int n,m;
while(cin>>n>>m)
{
char chain[30];
int h[30];
int l[30];
for(int i=0;i<n;i++)
{
cin>>chain[i]>>h[i]>>l[i];
}
char test[3][105];
for(int i=0;i<m;i++)
{
cin>>test[i];
}
int key;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(test[i][0]==chain[j])
{
key=j;
break;
}
}
p[0]=h[key];
p[1]=l[key];
int len=strlen(test[i]);
int flag=1;
for(int k=1;k<len;k++)
{
for(int j=0;j<n;j++)
{
if(test[i][k]==chain[j])
{
key=j;
break;
}
}
if(p[k]==h[key])
{
p[k+1]=l[key];
}
else
{
cout<<"MengMengDa"<<endl;
flag=0;
break;
}
}
if(flag==1)
{
cout<<maxchain(len)<<endl;
}
}
}
}
问题 C: 01背包问题
题目描述
已知有N种物品和一个可容纳C重量的背包。每种物品i的重量为Wi，价值为Pi。那么，采用怎样的装包方法才会使装入背包物品的总价值最大。
输入
包含多组测试数据。第一行为一个整数T(1<=T<=10)，代表测试数据个数。
接下来有T组测试数据。每组测试数据第一行为背包的重量C(C<10000)和物品个数N(N<1000)。接下来的N行分别为物品的重量cost(1<=cost<=100)和价值val(1<=val<=3000000)。（注意：结果可能超过int范围）
输出
对每组测试数据，输出其对应的所装物品的最大价值。
样例输入
1
10 5
2 6
2 3
6 5
5 4
4 6
样例输出
15
提示
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long w[10010],v[10010],dp[10010];
int t,m,n;
cin>>t;
while(t--)
{
cin>>m>>n;
for(int i=1;i<=n;i++)
{
cin>>w[i]>>v[i];
}
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
for(int j=m;j>=w[i];j--)
{
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
for(int i=m;i>=2;i--)
{
if(dp[i]!=dp[i-1])
{
cout<<dp[i]<<endl;
break;
}
}
}
return 0;
}
问题 D: 最大子段和
题目描述
给定n个整数组成的序列a1,a2,…an, 求子段和ai+ai+1+…+aj（子段可为空集）的最大值。
输入
包含多组测试数据。第一行为一个整数T(1<=T<=20)，代表测试数据个数。
每组测试数据第一行为一个整数n，代表有n个整数(1<=n<=10000)。
接下来一行有n个数x(-1000<=x<=1000)。
输出
输出其对应的最大子段和。
样例输入
1
6
2 -11 4 13 -1 2
样例输出
18
提示
子段可为空集，答案为0
代码
#include<bits/stdc++.h>
using namespace std;
int a[10010];
int sum=0;
int maxsum(int n)
{
int b=0;
for(int i=0;i<n;i++)
{
if(b>0)
{
b+=a[i];
}
else
{
b=a[i];
}
if(b>sum)
{
sum=b;
}
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
int k;
cin>>k;
for(int i=0;i<k;i++)
{
cin>>a[i];
}
maxsum(k);
cout<<sum<<endl;
}
return 0;
}
问题 E: 汽水瓶【25】
题目描述
有这样一道智力题：“某商店规定：三个空汽水瓶可以换一瓶汽水。小张手上有十个空汽水瓶，她最多可以换多少瓶汽水喝？”答案是5瓶，方法如下：先用9个空瓶子换3瓶汽水，喝掉3瓶满的，喝完以后4个空瓶子，用3个再换一瓶，喝掉这瓶满的，这时候剩2个空瓶子。然后你让老板先借给你一瓶汽水，喝掉这瓶满的，喝完以后用3个空瓶子换一瓶满的还给老板。如果小张手上有n个空汽水瓶，最多可以换多少瓶汽水喝？
输入
输入文件最多包含10组测试数据，每个数据占一行，仅包含一个正整数n(1≤n≤100)，表示小张手上的空汽水瓶数。n=0表示输入结束，你的程序不应当处理这一行。
输出
对于每组测试数据，输出一行，表示最多可以喝的汽水瓶数。如果一瓶也喝不到，输出 0
样例输入
3
10
81
0
样例输出
1
5
40
提示
代码
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main(){
int n,sum=0;
while(cin>>n&&n!=0){
sum=0;
while(n>2){
sum+=n/3;
n=(n%3)+(n/3);
}
if(n==2) sum++;
cout<<sum<<endl;
}
}
