前言

最近考试考得挺多的……这次算，考得还行？$\text{rk16}$。

话说 Peter 崛起了啊，$\text{rk7}$……

然鹅我和他都因为数组开小少得了 $\text{60pts}$​。以后别犯这种低级错误了啊……

OJ 最终成绩：$40+100+55+5+0=200$​

Lemon 上不知道。

快乐的题解时间

T1

题意简述：

有 $T$ 组数据，每组数据给定 $n$ 个数字，记为 $a_1,a_2,\ldots a_n$。在这一组数据中选出 $5$ 个数字使得这 $5$ 个数字的乘积最大。

果然是不开 long long 见祖宗啊……

还有就是数组开小，后 $10$ 个点全 RE 了……

我直接 AC $\text{100pts}→$ WA + RE $\text{40pts}$……

法一：贪心

我们知道乘积要最大，一定要让它尽量为正数。

那么，首先我们先按照绝对值的大小将数组从大到小排序。然后我们看一看：

  1. 如果前 $5$ 个数字中有 $0$，那说明这组数据中不为 $0$ 的数少于 $5$ 个。那么结果一定为 $0$。

  2. 如果前 $5$ 个数字的乘积为正数，那么这个乘积一定是最优解。证明很简单，相信大家都明白。

那么如果这 $5$ 个数的乘积是负数呢？

那么首先我们分析最小那个数（即第 $5$ 个数）是否可以被换成一个和它正负相反的数字。因为我们知道，当一个乘积为负的时候，只需要换一个就可以了。找当然是从前往后找，找到一个就立刻输出，然后 return。因为这已经是最优解了。

继续，如果找不到怎么办？那我们就找与 $a_4,a_3,a_2,a_1$ 正负相反的数来代替它（此时的 $a$ 数组已经排过序，还是按照绝对值从大往小找保证找到的是最优解，当然，前 $4$ 个数字要从小往大找）。

那如果还是找不到呢？那么，这组数据一定是不能凑出正数。那么我们就只能找绝对值最小的 $5$ 个数（包括 $0$）来凑乘积了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,a[100005];
bool f;
bool cmp(int x,int y){return abs(x)>abs(y);}
bool cmp2(int x,int y){return abs(x)<abs(y);}
void s(){
    int h=0;
    bool b[15]={};
    for(int i=1;i<=5;i++){
        b[i]=(a[i]<0);
        h+=(int)b[i];
        if(!a[i]){
            printf("0\n");
            return;
        }
    }
    if(!(h&1)){
        printf("%lld\n",a[1]*a[2]*a[3]*a[4]*a[5]);
        return;
    }
    bool d=!b[5];
    for(int i=6;i<=n;i++){
        if((a[i]<0)==d){
            printf("%lld\n",a[1]*a[2]*a[3]*a[4]*a[i]);
            return;
        }
    }
    for(int i=4;i;i--){
        if(b[i]!=b[5]){
            int y=a[1]*a[2]*a[3]*a[4]*a[5];
            y/=a[i];
            for(int j=6;j<=n;j++){
                if((a[j]<0)!=b[i]){
                    y*=a[j];
                    printf("%lld\n",y);
                    return;
                }
            }
        }
    }
    sort(a+1,a+n+1,cmp2);
    printf("%lld\n",a[1]*a[2]*a[3]*a[4]*a[5]);
    return;
}
signed main(){
    freopen("maximum.in","r",stdin);
    freopen("maximum.out","w",stdout);
    scanf("%lld",&t);
    while(t--){
        f=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]),f=f|(!a[i]);
        sort(a+1,a+n+1,cmp);
        s();
    }
    return 0;
}

法二：DP

As we all know，最大的乘积是有可能从最小的数（绝对值比较大）乘一个负数得到~

所以，如果我们使用 DP 来求解这个问题的话，需要开两个 $dp$ 数组来分别存最大值和最小值。

如果要求最大值（至少得是个正数吧），有两种方法来求：

  1. 两个正数（其中一个是前面的最大值）相乘；

  2. 两个负数（其中一个是前面的最小值）相乘。

求最小值也有两种方法，不过我现在用的这个电脑输入法实在是太不好用了，所以我真的不想写了。。。

见代码……

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t,n,a[100005];
ll dp1[100005][6],dp2[100005][6];
signed main(){
    freopen("maximum.in","r",stdin);
    freopen("maximum.out","w",stdout);
    scanf("%d",&t);
    while(t--){
        memset(dp1,128,sizeof(dp1));
        memset(dp2,127,sizeof(dp2));
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=0;i<=n;i++) dp1[i][0]=dp2[i][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=min(i,(int)5);j++){
                dp1[i][j]=max(max(dp1[i-1][j-1]*a[i],dp2[i-1][j-1]*a[i]),dp1[i-1][j]);
                dp2[i][j]=min(min(dp1[i-1][j-1]*a[i],dp2[i-1][j-1]*a[i]),dp2[i-1][j]);
            }
        }
        printf("%lld\n",dp1[n][5]);
    }
    return 0;
}

T2

水题，打表即可……

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
//有亿点长的打表代码 qwq
#include<bits/stdc++.h>
using namespace std;
int I,V,X,L,C,D,M,n;
string sc(int x){
    int qian=x/1000;
    x%=1000;
    int bai=x/100;
    x%=100;
    int shi=x/10;
    x%=10;
    string s;
    //千位
    if(qian==1) s="M";
    else if(qian==2) s="MM";
    else if(qian==3) s="MMM";
    //百位
    if(bai==1) s+="C";
    else if(bai==2) s+="CC";
    else if(bai==3) s+="CCC";
    else if(bai==4) s+="CD";
    else if(bai==5) s+="D";
    else if(bai==6) s+="DC";
    else if(bai==7) s+="DCC";
    else if(bai==8) s+="DCCC";
    else if(bai==9) s+="CM";
    //十位
    if(shi==1) s+="X";
    else if(shi==2) s+="XX";
    else if(shi==3) s+="XXX";
    else if(shi==4) s+="XL";
    else if(shi==5) s+="L";
    else if(shi==6) s+="LX";
    else if(shi==7) s+="LXX";
    else if(shi==8) s+="LXXX";
    else if(shi==9) s+="XC";
    //个位 
    if(x==1) s+="I";
    else if(x==2) s+="II";
    else if(x==3) s+="III";
    else if(x==4) s+="IV";
    else if(x==5) s+="V";
    else if(x==6) s+="VI";
    else if(x==7) s+="VII";
    else if(x==8) s+="VIII";
    else if(x==9) s+="IX";
    return s;
}
int main(){
    freopen("introduction.in","r",stdin);
    freopen("introduction.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        string s=sc(i);
        int j=0;
        while(s[j]){
            if(s[j]=='I') I++;
            else if(s[j]=='V') V++;
            else if(s[j]=='X') X++;
            else if(s[j]=='L') L++;
            else if(s[j]=='C') C++;
            else if(s[j]=='D') D++;
            else if(s[j]=='M') M++;
            j++;
        }
    }
    if(I) printf("I %d\n",I);
    if(V) printf("V %d\n",V);
    if(X) printf("X %d\n",X);
    if(L) printf("L %d\n",L);
    if(C) printf("C %d\n",C);
    if(D) printf("D %d\n",D);
    if(M) printf("M %d\n",M);
    return 0;
}

T3

和 LIS 问题的普通版求解差不多，只是需要多开一维记录前一个是上升还是下降。

zmq 说也可以用贪心统计折点的数量再 $+1$，但是我交了之后只有 $\text{45pts}$，也不知道是我实现错了还是他说错了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
int n,num,dp[10005][2],a[10005];
bool b[10005];//0为上升，1为下降
int main(){
    freopen("sawtooth.in","r",stdin);
    freopen("sawtooth.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    dp[1][0]=dp[1][1]=1;
    for(int i=2;i<=n;i++){
        for(int j=1;j<i;j++){
            if(a[i]<a[j]) dp[i][0]=max(dp[i][0],dp[j][1]+1);
            if(a[i]>a[j]) dp[i][1]=max(dp[i][1],dp[j][0]+1);
        }
        num=max(num,max(dp[i][0],dp[i][1]));
    }
    printf("%d",num);
    return 0;
}

T4

$dp_{i,j}$ 表示前 $i$ 只 mjl 马进前 $j$ 个马棚产生的最小不愉快系数。

对于每一只 mjl 马，我们可以把它和它前面的 一些 mjl 马一起装在一个马棚里，说具体点，就是再用一层循环，$q$ 代表从第 $q$ 只 mjl 马开始就和第 $i$ 只 mjl 马装在一个马棚里。这样产生的不愉快系数就是 $dp_{q-1,j-1}$ + 这个马棚里的不愉快系数。那这个不愉快系数怎么算呢？用前缀和统计一下这个区间里黑 mjl 马和白 mjl 马的数量再相乘就可以了。具体看代码。

$dp$ 初始化成 $\text{INF}$，$dp_{0,0}=0$。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
int n,k,a[505],b[505],w[505],dp[505][505];
int main(){
    freopen("horse.in","r",stdin);
    freopen("horse.out","w",stdout);
    memset(dp,127,sizeof(dp));
    dp[0][0]=0;
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        w[i]=w[i-1]+(!a[i]);
        b[i]=b[i-1]+a[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=min(i,k);j++){
            for(int q=j;q<=i;q++){
                dp[i][j]=min(dp[i][j],dp[q-1][j-1]+(w[i]-w[q-1])*(b[i]-b[q-1]));
            }
        }
    }
    printf("%d",dp[n][k]);
    return 0;
}

T5

$50$ 分就是一个分组背包。

$100$ 分好像是要开专门记录有或者没有奖励子弹的情况。

没太听明白，放个代码留在这吧。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;
int m,n,k;
int f[205][205];
bool h[205][205];
char a;
int dy[205][205],dn[205][205],dpy[205][205],dpn[205][205];
int main(){
    scanf("%d %d %d",&m,&n,&k);
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            scanf("%d %c",&f[i][j],&a);
            if(a=='Y') h[i][j]=1;
        }
    }
    //初始化dy和dn的值 
    for(int i=1;i<=n;i++){ //列 
        int tot=0;
        for(int l=m;l;l--){ //行 
            if(h[l][i]){
                dy[i][tot]+=f[l][i];
                //dn[i][tot]=dy[i][tot];
            }else{
                tot++;
                dn[i][tot]=dy[i][tot-1]+f[l][i];
                dy[i][tot]=dn[i][tot];
            }
        }
    }
    //状态转移 
    for(int i=1;i<=n;i++){ //列 
        for(int j=0;j<=k;j++){ //子弹的数量 
            for(int q=0;q<=min(k,j);q++){ //当前这一列子弹的数量 
                //打第i列最后打到Y，并且把这个奖励子弹用在后面 
                dpy[i][j]=max(dpy[i][j],dpy[i-1][j-q]+dy[i][q]);
                //打第i列打到N
                if(q) dpn[i][j]=max(dpn[i][j],dpy[i-1][j-q]+dn[i][q]);
                //打第1~i-1列的N
                if(j-q) dpn[i][j]=max(dpn[i][j],dpn[i-1][j-q]+dy[i][q]);
            }
        } 
    }
    printf("%d",dpn[n][k]);
    return 0;
}