2019-10-24测试总结

$merge$

题目大意

有$n(1 \leqslant n \leqslant 300)$个只有$1$个数字的集合呈环形排列，并集操作$S \bigcup T$会产生$|S| * |T|$的收益，其中$|S|$表示集合$S$的元素个数，现在给定这$n$个数字，第i个数字为$a_i$($1 \leqslant a_i \leqslant n$)，求合并到只剩下最后一个数字的时候能获得的最大的收益之和

环形区间$dp$水题

首先一个区间所合并之后的元素个数是固定的，所以可以$O(n ^ 3)$预处理一遍

然后就是直接环形区间$dp$即可

但是注意是环形的所以控制区间的位置要注意细节

最后就是我考场上写的$map$但是可以直接开$bool$数组，活活炸掉$50$分

然后我也没有查找长度为$n$的区间最大值而是直接输出$f[1][n]$

然后我的区间处理也有问题

所以就爆$0$了

更正后的代码:

#include<cstdio>
#include<algorithm>
using namespace std;
#define file(SSS) freopen(SSS".in","r",stdin),freopen(SSS".out","w",stdout)
#define file_close fclose(stdin),fclose(stdout)

#define MAXN 605
int n,a[MAXN][MAXN],dp[MAXN][MAXN];
int t[MAXN];
bool e[MAXN][MAXN][MAXN >> 1];
int main()
{
    file("merge");

    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
    {
        scanf("%d",&t[i]),t[i + n] = t[i];
        a[i][i] = 1,a[i + n][i + n] = 1,e[i + n][i + n][t[i]] = 1;
    }

    for(int len = 1;len < n;len ++)
    for(int i = 1;i <= 2 * n - 1 - len;i ++)
    for(int k = i;k <= i + len;k ++)
        if(!e[i][i + len][t[k]]) e[i][i + len][t[k]] = 1,a[i][i + len] ++;

    for(int len = 1;len < n;len ++)
    for(int i = 1;i <= 2 * n - 1 - len;i ++)
    for(int k = i;k < i + len;k ++)
    dp[i][i + len] = max(dp[i][i + len],
    dp[i][k] + dp[k + 1][i + len] + a[i][k] * a[k + 1][i + len]);

    int Max = 0;
    for(int i = 1;i < n;i ++)
        if(dp[i][i + n - 1] > Max) Max = dp[i][i + n - 1];
    printf("%d",Max);

    file_close;
    return 0;
}

$climb$

题目大意

有$n(n \leqslant 10^5)$个操作，目标高度$L$，第$i$个操作可以使高度升高$a_i$，并在升高后下降$b_i$，每次操作最多使用$1$次,同时每次操作之后的高度都不能低于$\sum\limits_{j = 1}^{i} c_j$，$a_i,b_i,c_i$满足$0 \leqslant a_i,b_i,c_i \leqslant 10^9$,任何时候，当高度满足高度$h >= L$时，操作结束，求最少操作数

贪心思路

首先先看当前高度下最大的$a_i$是否满足$a_i \geqslant L - h$，如果满足就可以直接结束操作

否则看当前高度$h += a_i - b_i$，且在$a_i - b_i == a_j - b_j$时，先做$a_i$小的操作，以保证当前高度在下一次能够用最大的$a_i$更新

贪心的正确性

我们主要是考虑在选定了最大的$a_i - b_i$之后，是不是会浪费掉一个比较大的$a_i$

然后发现在找贪心的正确性的时候发现了贪心的错误

Hack数据

显然原来的选择策略变成了错误的

然后就发现标程从300被卡成了290

还是放一下考场上的代码：

#include<cstdio>
#include<queue>
using namespace std;
#define file(SSS) freopen(SSS".in","r",stdin),freopen(SSS".out","w",stdout)
#define file_close fclose(stdin),fclose(stdout)

#define MAXN 100005
int n,l;
struct MED1
{
    int a,b,r,num;
    bool operator < (const MED1 &c) const
    {
        if(r == c.r) return a > c.a;
        else return r < c.r;
    }
}m1[MAXN];
struct MED2
{
    int a,num;
    bool operator < (const MED2 &c) const {return a < c.a;}
}m2[MAXN];
bool vis[MAXN];
int sum[MAXN];
priority_queue<MED1> p;
priority_queue<MED2> q;
int main()
{
    file("climb");
    scanf("%d%d",&n,&l);
    for(int i = 1;i <= n;i ++)
    {
        scanf("%d%d",&m1[i].a,&m1[i].b);
        m1[i].r = m1[i].a - m1[i].b,m1[i].num = i;
        m2[i].a = m1[i].a,m2[i].num = i;
        p.push(m1[i]),q.push(m2[i]);
    }
    for(int i = 1;i <= n;i ++)
    {
        int x;scanf("%d",&x);
        sum[i] = sum[i - 1] + x;
    }
    int h = 0,cnt = 0;
    bool flag = 0;
    while(h < l)
    {
        MED2 temp = q.top();
        while(vis[temp.num] && !q.empty()) q.pop(),temp = q.top();
        if(q.empty()){flag = 1;break;}
        if(h + temp.a >= l){cnt ++;break;}
        MED1 TEMP = p.top();
        while(vis[TEMP.num]) p.pop(),TEMP = p.top();
        vis[TEMP.num] = 1;
        h += TEMP.r;
        if(h <= sum[++cnt]){flag = 1;break;}
    }
    if(!flag) printf("%d",cnt);
    else puts("-1");
    file_close;
    return 0;
}

$coin$

高级博弈论，不会