常州集训 Day1

打比赛

第一题：输入输出TLE了，成为了CMX，成功少了20分，数据量大少用cin/cout警钟长鸣。

第二题：二分炸掉了，后面改对了，非常玄学

select
首先对每个班级的身高进行排序，方便之后使用二分法查询适合的身高。
依次假设每一位同学的身高是最小身高，找出该情况下的最优方案，即从每个班级找一位不矮于该同学的最小身高的同学（在每个班级中使用二分查找），得出该情况的最小身高差。
从所有情况的最小身高差中找到最小值做为答案。

第三题：很普通的搜索，轻松AC。

第四题：看起来很像状压dp骗到10分
贴一下第四题代码

candy
桌子上横着一排N颗糖，从左到右序号从1到N。糖果的美味度是Ai。小A决定从N颗糖中选几颗吃。

但是，为了不吃过多的糖，无论是哪一种连续的K颗糖，最多只能吃2颗。也就是说，对于任何一个j(1 <= j <= N-K+1)，从糖j到糖j+K-1的连续K颗糖中，吃的糖的个数不得多于2颗。

在此基础上，小A想尽量增大吃糖的美味度的总和。当给予N颗糖的美味度 和 K时，请编写程序，求出小A所吃糖的美味度之和的最大值。

#include <bits/stdc++.h>
using namespace std;
int n,k,a[3011],dp[3011][511],ans=0;
bool vis[3011];
int main()
{
    freopen("candy.in","r",stdin);
    freopen("candy.out","w",stdout);
    cin >> n >> k;
    for(int i=1;i<=n;i++) cin>>a[i];
    memset(dp,-1,sizeof dp);
    dp[1][0]=0,dp[1][1]=a[1];
    //i目标行 j转移行 k糖果数量 w转移糖果数量 
    for(int i=2;i<=n;i++)
    {
        dp[i][0]=dp[i-1][0];
        dp[i][1]=max(dp[i-1][1],dp[i-1][0]+a[i]);
        if(i >= 2) dp[i][2]=max(dp[i-1][2],dp[i-1][1]+a[i]);
        for(int j=i-1;j>i-k&&j>=0;j--) dp[i][2]=max(dp[i][2],dp[j][1]+a[i]);
        for(int j=1;j<=i-k;j++) 
        {
            for(int k=2;k<=n;k++)
            {
                for(int w=1;w<=k;w++)
                {
                    if(dp[j][w]+dp[i][k-w] > dp[i][k]&&!vis[j])
                    {
                        dp[i][k]=dp[j][w]+dp[i][k-w];
                        vis[j]=1;
                    }
                } 
            }
        }
    }
    for(int i=1;i<=n;i++) ans=max(ans,dp[n][i]);
    cout << ans; 
    return 0;
}

题解

由于前k个糖果最多只会吃两个，因此考虑只保存前面吃掉的2个的DP。
dp[i][j]:表示最后吃的是糖i，倒数第二个吃的是糖j时，美味之和的最大值，
将所有(i，j)的DP [i][j]的最大值作为答案即可。
注意，由于限制，总是吃2个以上的解是最优的,即不可能有最优解只吃一个糖果，所以不用考虑只吃一个糖果的情况。
dp[i][j] ← max{ dp[j][k] | k ≦ min(j-1, i-K) } + Ai
此时时间复杂度为O(n^3),需要进一步简化
在进行递归时，维护dp[i][j]=max(dp[i][j-1],dp[i][j]),因为（i，j）一定符合（i，j-1）的条件。
此时状态转移方程简化为dp[i][j] ← dp[j][i-k] + Ai
时间复杂度为O(n^2)

#include <bits/stdc++.h>
using namespace std;
const long long INF = 1<< 60;
int main() {
    freopen("candy.in","r",stdin);
    freopen("candy.out","w",stdout);
    int N, K;
    cin >> N >> K;
    vector<long long> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    vector<vector<long long> > dp(N, vector<long long>(N, -INF));
    long long res = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < i; j++) {
            if (j > 0) {
                dp[i][j] = dp[i][j - 1];
            }
            dp[i][j] = max(dp[i][j], A[i] + A[j]);
            if (0 <= i - K && j > 0) {
                dp[i][j] = max(dp[i][j], dp[j][min(j - 1, i - K)] + A[i]);
            }
            res = max(res, dp[i][j]);
        }
    }
    cout << res << endl;
    fclose(stdin);
    fclose(stdout);
    return 0;
}