B题 最长公共子序列

题面

样例

思路

首先已知所求的是两个排列的最长公共子序列，如果二者有公共子序列，那么这个子序列的各个元素在P1出现的顺序一定和在P2出现的顺序是一样的。
我们实际上可以做的是以P1为基准，将P2中的元素与P1中的元素进行匹配。也就是说现在我们假设将P1数组存在一个离散化的数组中，数组的下标为1 2 3 4 5 6......然后我们现在做的其实是将找P2数组中的数存在与P1的哪个位置，就这样我们可以得到一个新的数组，这个数组是P2中的元素在P1中的排列顺序中对应的下标。
前面说了这个公共子序列出现的顺序一样，我们现在假设的是P1的下标为1 2 3 4 5 6......为升序，那么刚刚得到新的数组的元素也应该是升序。
由此问题就可以转化为新数组中的最长上升子序列问题

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
//这题是求两个排列的最长公共子序列。
//因为排列的特殊性，我们可以将问题转换为以P1顺序标号的P2的排序数组的最长上升子序列问题。
int _index[N];
int x[N];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    //
    int n;cin >> n;
    for(int i = 1;i <= n;++i)
    {
        int temp;
        cin >> temp;
        //这个地方直接交换i和temp就行，因为i本身就是有序的。
        _index[temp] = i;
    }
    //将数组设为无穷大方便lower_bound操作
    //也就是免去了判断num是否大于最大值的操作
    memset(x, 0x3f3f3f, sizeof(x));
    for(int i = 1;i <= n;++i)
    {
        int temp;cin >> temp;
        //直接得到P2的下标
        int num = _index[temp];
        int pos = lower_bound(x+1, x+1+n, num)-x;
        x[pos] = num;
    }
    //
    int ans = 0;
    //如果走到了正无穷处，那他的前一位就是答案了
    for(int i = 1;i <= n+1;++i) if(x[i] > n) {ans = i-1;break;}
    cout << ans << endl;
    return 0;
}

E题 CD

题面

题意

你有n个音乐片段和N个长度的时间，每段音乐都要播放一定长度的时间，现在问你如何刻录这n个音乐使得在不超过N的时限内刻录的音乐总时长最长。

样例

思路

这题一眼就知道是01背包，但是主要是要得到路径，那么我们可以用01背包的二维dp形式，因为我们需要得到每一层所存储的值，根据状态转移方程逆推即可得到所选取的CD

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 30;
//这题就是01背包
int num[maxn];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    //
    int N, n;
    while(cin >> N >> n)
    {
        for(int i = 1;i <= n;++i) cin >> num[i];
        vector<vector<int> >dp(N+1, vector<int>(N+1, 0));
        //
        for(int i = 1;i <= n;++i)
        {
            for(int j = 1;j <= N;++j)
            {
                dp[i][j] = dp[i-1][j];
                if(j >= num[i]) dp[i][j] = max(dp[i-1][j], dp[i-1][j-num[i]]+num[i]);
            }
        }
        //由上面的式子我们可以知道，如果选中了num[i]
        //那么恒有dp[i][t] - dp[i-1][t-num[i]] == num[i]，其中t为当前体积
        //所以可以反推回原序列
        int t = dp[n][N];
        for(int i = n;i >= 1;--i)
        {
            if(dp[i][t] - dp[i-1][t-num[i]] == num[i])
            {
                cout << num[i] << " ";
                t -= num[i];
            }
        }
        cout << "sum:" << dp[n][N] << endl;
    }
    return 0;
}

G题 Flipping coins

题面

题意

原先有n枚硬币反面朝上，现在你必须投掷K次硬币，每次投掷硬币可能会使得硬币变成正面或者反面，现在你想要让正面朝上的硬币数量最多，请输出投了K次硬币之后硬币正面朝上个数的期望。

思路

（等待更新中.....）