算法課第五次作業(yè)
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)，長度之和最大狀態(tài)即為解

#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;
}

優(yōu)化思路

函數lis()和lds()顯然可以合一

B.加分二叉樹

題目描述
　　設一個n個節(jié)點的二叉樹tree的中序遍歷為（l,2,3,…,n），其中數字1,2,3,…,n為節(jié)點編號。每個節(jié)點都有一個分數（均為正整數），記第i個節(jié)點的分數為di，tree及它的每個子樹都有一個加分，任一棵子樹subtree（也包含tree本身）的加分計算方法如下：
　　subtree的左子樹的加分× subtree的右子樹的加分＋subtree的根的分數
　　若某個子樹為空，規(guī)定其加分為1，葉子的加分就是葉節(jié)點本身的分數。不考慮它的空子樹。
　　試求一棵符合中序遍歷為（1,2,3,…,n）且加分最高的二叉樹tree。要求輸出；
　?。?）tree的最高加分
　?。?）tree的前序遍歷
輸入數據
第 1 行：一個整數 n （n＜30），為節(jié)點個數。
第 2 行： n 個用空格隔開的整數，為每個節(jié)點的分數（分數＜100）。
輸出數據第 1 行：一個整數，為最高加分（結果不會超過 4,000,000,000 ）。
第 2 行： n 個用空格隔開的整數，為該樹的前序遍歷。
若存在多種前序遍歷均為最高加分，則輸出字典序最小的前序遍歷
樣例輸入
5
5 7 1 2 10
樣例輸出
145
3 1 2 4 5

解題思路

區(qū)間動態(tài)規(guī)劃
由于二叉樹的中序遍歷為1, 2, 3, ..., n，因此該二叉樹的特點是：當根節(jié)點為k時，編號小于k的結點都在其左子樹上，而大于k的結點都在其右子樹上。這個特點符合區(qū)間動態(tài)規(guī)劃的特性。
兩個dp數組dp[i][j]存從i到j的最大權值
root[i][j]存i到j的最優(yōu)根(方便輸出)

#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個無區(qū)別實體劃分為不超過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.統(tǒng)計單詞個數

題目描述
　　給出一個長度不超過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

思路

先確定用什么表示狀態(tài)，因為遞推過程中有兩個變量——當前字母的位置，以及所分的部分。
那么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]這個區(qū)間的單詞數，可用調用api實現：
在做這道題之前，先了解以下幾個的STL函數。

• s.substr(x,y) 在s中取出下標從x開始長度為y的字符串(第一個字母下標為0)；
• s.find(t) 在s中尋找字符串t，找到則返回0，找不到則返回一個極大值；
• s.length() 返回字符串s的長度；

題目要求說一個字母只能是一個單詞的開頭。
那么我們考慮倒序。
首先，我們從右往左枚舉區(qū)間右端點。
然后從在右往左枚舉區(qū)間左端點，先繼承上一個左端點的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點。卒行走的規(guī)則：可以向下、或者向右。同時在棋盤上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;
}

代碼欠優(yōu)化。空間，代碼量都不佳。