算法课第五次作业
BJTU计算思维与算法实训平台
A.合唱队形
题目描述
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足T1< ...< Ti> Ti+1> …> TK(1< =i< =K)。你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
输入数据
输入的第一行是一个整数 N (2≤ N≤ 100) ，表示同学的总数。第一行有 n 个整数，用空格分隔，第 i 个整数 Ti (130≤ Ti≤ 230) 是第 i 位同学的身高(厘米)。
输出数据
输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。
样例输入
8
186 186 150 200 160 130 197 220
样例输出
4
解题思路
此问题是LIS问题的变形，即把整数列分成左右两半，求左半边的LIS(Longest Increasing Subsequence)，右半边的LDS(Longest Decreasing Subsequence)，长度之和最大状态即为解
#include <iostream>
#include <cstring>
#define MAX_N 1000
using namespace std;
int n;
int a[MAX_N];
int dp[MAX_N],dp2[MAX_N];
//a[0]~a[k-1]
int lis(int k) {
int res = 0;
for (int i = 0; i < k; i++) {
dp[i] = 1;
for (int j = 0; j < k; j++) {
if (a[i] > a[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
res = max(res, dp[i]);
}
}
return res;
}
//a[k]~a[n-1]
int lds(int k) {
int res = 0;
for (int i = k; i < n; i++) {
dp2[i] = 1;
for (int j = k; j < n; j++) {
if (a[i] < a[j]) {
dp2[i] = max(dp2[i], dp2[j] + 1);
}
res = max(res, dp2[i]);
}
}
return res;
}
int main() {
cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i];
int sol = 0;
for(int i = 0; i < n; i++){
sol = max(sol, lis(i) + lds(i));
memset(dp,0,sizeof(dp));
memset(dp2,0,sizeof(dp2));
}
cout << n - sol;
return 0;
}
优化思路
函数lis()和lds()显然可以合一
B.加分二叉树
题目描述
设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：
subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数
若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。
试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。要求输出；
（1）tree的最高加分
（2）tree的前序遍历
输入数据
第 1 行：一个整数 n （n＜30），为节点个数。
第 2 行： n 个用空格隔开的整数，为每个节点的分数（分数＜100）。
输出数据第 1 行：一个整数，为最高加分（结果不会超过 4,000,000,000 ）。
第 2 行： n 个用空格隔开的整数，为该树的前序遍历。
若存在多种前序遍历均为最高加分，则输出字典序最小的前序遍历
样例输入
5
5 7 1 2 10
样例输出
145
3 1 2 4 5
解题思路
区间动态规划
由于二叉树的中序遍历为1, 2, 3, ..., n，因此该二叉树的特点是：当根节点为k时，编号小于k的结点都在其左子树上，而大于k的结点都在其右子树上。这个特点符合区间动态规划的特性。
两个dp数组dp[i][j]存从i到j的最大权值
root[i][j]存i到j的最优根(方便输出)
#include <iostream>
#include <cstring>
#define N 31
using namespace std;
typedef long long ll;
//di < 4,000,000,000
ll n, dp[N][N], root[N][N];
void output(int l, int r) {
if(l>r) return;
cout<<root[l][r]<<" ";
if(l==r) return;
output(l,root[l][r]-1);
output(root[l][r]+1,r);
}
int main() {
cin>>n;
//init d[i] f[i]
memset(dp,0,sizeof(dp));
for(int i=1; i<=n; i++) {
cin>>dp[i][i];
root[i][i] = i;
}
//对len长的树
for(int len=1; len<n; len++) {
for(int i=1; i+len<=n; i++) {
int j=i+len;
for(int k=i; k<j; k++) {
ll maxw = dp[i][k-1]*dp[k+1][j]+dp[k][k];
if(!dp[i][k-1]) maxw = dp[k+1][j]+dp[k][k];
if(!dp[k+1][j]) maxw = dp[i][k-1]+dp[k][k];
if(dp[i][j]<maxw) {
dp[i][j]=maxw;
root[i][j]=k;
}
}
}
}
cout<<dp[1][n]<<endl;
output(1,n);
return 0;
}
C.采药
同01背包问题，略
D.数的划分
题目描述
将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。
例如：n=7，k=3，下面三种分法被认为是相同的。
1,1,5; 1,5,1; 5,1,1;
问有多少种不同的分法。
输入数据
输入 n ， k (6< n≤ 200 ， 2≤ k≤ 6)
输出数据
一个整数，即不同的分法。
样例输入
7 3
样例输出
4
思路
划分数问题描述
n个无区别实体划分为不超过m组求方法数
递推关系如下(dp[i][j]表示j的i划分)
dp[ i ][ j ] = dp[i - 1][ j ] + dp[ i ][ j - i ]
即j的i-1划分加i的j-i划分
则本题代码如下
#include<iostream>
#include<cstring>
using namespace std;
#define MAX_N 200
#define MAX_M 6
int dp[MAX_M][MAX_N];//n的m划分
int n,m;
int main() {
cin>>n>>m;
n-=m;
memset(dp,0,sizeof(dp));
int res=0;
dp[0][0] = 1;
//dp[i][j];j的i划分
for(int i = 1; i <= m; i++) {
for(int j = 0; j <= n; j++) {
if(j - i >= 0)
dp[i][j] = (dp[i - 1][j] + dp[i][j - i]);
else
dp[i][j] = dp[i - 1][j];
}
}
cout<<dp[m][n];
return 0;
}
E.统计单词个数
题目描述
给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入，且保证每行一定为20个)。要求将此字母串分成k份(1< k< =40)，且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可包含this和is，选用this之后就不能包含th)。
单词在给出的一个不超过6个单词的字典中。
要求输出最大的个数。
输入数据
第一行有二个正整数 (p ， k)
p 表示字串的行数;
k 表示分为 k 个部分。
接下来的 p 行，每行均有 20 个字符。
再接下来有一个正整数 s ，表示字典中单词个数。 (1≤ s≤ 6)
接下来的 s 行，每行均有一个单词。
输出数据
输出一个整数，即最大的个数
样例输入
1 3
thisisabookyouareaoh
4
is
a
ok
sab
样例输出
7
思路
先确定用什么表示状态，因为递推过程中有两个变量——当前字母的位置，以及所分的部分。
那么dp[i][j]表示到第i个字母为止，分成j份 的最多单词数。
核心算法是
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=i;k>=j;k--)
dp[i][j]=max(dp[i][j],dp[k-1][j-1]+w);
w表示[k~i]这个区间的单词数，可用调用api实现：
在做这道题之前，先了解以下几个的STL函数。
-
s.substr(x,y)在s中取出下标从x开始长度为y的字符串(第一个字母下标为0)； -
s.find(t)在s中寻找字符串t，找到则返回0，找不到则返回一个极大值； -
s.length()返回字符串s的长度；
题目要求说一个字母只能是一个单词的开头。
那么我们考虑倒序。
首先，我们从右往左枚举区间右端点。
然后从在右往左枚举区间左端点，先继承上一个左端点的sum，在判断当前的这个左端点是否能作为某个单词的开头。
如果能就+1.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int dp[1000][100],sum[1000][1000];
int p,k,m,len;
string s="0",ch,a[1000];
inline bool check(int l,int r){
string x=s.substr(l,r-l+1);
for(int i=1;i<=m;i++)
if(x.find(a[i])==0) return true;
return false;
}
int main()
{
int i,j,t;
scanf("%d%d",&p,&k);
for(i=1;i<=p;i++){
cin>>ch;
s+=ch;
}
scanf("%d",&m);
for(i=1;i<=m;i++) cin>>a[i];
len=s.length()-1;
for(i=len;i>=1;i--)
for(j=i;j>=1;j--){
sum[j][i]=sum[j+1][i];
if(check(j,i))
sum[j][i]++;
}
for(i=1;i<=len;i++)
for(j=1;j<=k&&j<=i;j++)
for(t=j;t<=i;t++)//dp核心
dp[i][j]=max(dp[i][j],dp[t-1][j-1]+sum[t][i]);
printf("%d",dp[len][k]);
}
(转自文雨淋)
F.马兰过河卒
题目描述
棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示，A点(0, 0)、B点(n, m)(n, m为不超过15的整数)，同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。
输入数据
一行四个数据，分别表示 B 点坐标和马的坐标。
输出数据
一个数据，表示所有的路径条数。
样例输入
6 6 3 3
样例输出
6
思路
考虑棋盘没🐎，卒(0,0)到达点(n,n)的路径数，显然等于到(n,n-1)加到(n-1,n)的路径数，递推关系就有了，顺便加上🐎这个限制条件便得到解
#include<cstring>
#include<iostream>
using namespace std;
const int dx[] = {-1,-1,1,1,2,2,-2,-2};
const int dy[] = {2,-2,2,-2,1,-1,1,-1};
bool chess[16][16];//chess[0][0] ~ chess[15][15]
int dp[16][16];//dp[x][y] = dp[x-1][y] + dp[x][y-1]
int ex,ey,mx,my;
bool inchess(int x,int y) {
return (x>-1 && x<16 && y>-1 && y<16);
}
int main() {
memset(chess,true,sizeof(chess));
memset(dp,0,sizeof(dp));
cin >> ex >> ey >> mx >> my;
chess[mx][my] = false;
dp[0][0] = 1;
for(int i=0; i<8; i++)
if(inchess(mx+dx[i],my+dy[i]))
chess[mx+dx[i]][my+dy[i]] = false;
dp[0][0] = 1;
for(int i=1; i<=ex; i++) {
if(chess[i][0])
dp[i][0] = dp[i-1][0];
else dp[i][0] = 0;
}
for(int j=1; j<=ey; j++) {
if(chess[0][j])
dp[0][j] = dp[0][j-1];
else dp[0][j] = 0;
}
for(int i=1; i<=ex; i++) {
for(int j=1; j<=ey; j++) {
if(chess[i][j]) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
} else dp[i][j] = 0;
}
}
cout << dp[ex][ey];
return 0;
}
代码欠优化。空间，代码量都不佳。
