P9676 [ICPC 2022 Jinan R] Skills

题目描述

庞博士有 $3$ 项技能：喝汽水、猎狐和炒股，编号分别为 $1,2,3$。初始时，每项技能的熟练度为 $0$。

接下来有 $n$ 天。在第 $i$ 天，庞博士可以选择一项技能（假设是第 $j$ 项）进行练习，然后在这天结束时让这项技能的熟练度增加 $a_{i,j}(0\le a_{i,j}\le 10000)$。同时，如果某一项技能（假设是第 $k$ 项）已经有 $x$ 天没有练习，那么在这天结束时，这项技能的熟练度会减少 $x$。当然，任何一项技能的熟练度都不可能小于 $0$。

现在，庞博士想知道：在第 $n$ 天结束后，这 $3$ 项技能的熟练度之和最大为多少。由于他非常忙，而且他的日程和对习惯的适应程度可能有变，所以庞博士把这 $T$ 个问题交给了你——每个问题的内容都一样，只是给出的数据可能有所不同而已。

输入格式

第一行，一个正整数 $T(1\le T\le 1000)$，表示数据组数。

对于每组数据，输入 $(n+1)$ 行。

• 第一行，一个正整数 $n(1\le n\le 1000)$，表示天数。
• 第 $i+1$ 行，包含三个正整数 $a_{i,1},a_{i,2},a_{i,3}(0\le a_{i,j}\le 10000,\forall 1\le i\le n,1\le j\le 3)$。

数据保证单个测试点内的 $\sum n$ 不超过 $1000$。

输出格式

对于每组数据，输出 $1$ 行 $1$ 个数，表示答案。

输入输出样例 #1

输入 #1

2
3
1 1 10
1 10 1
10 1 1
5
1 2 3
6 5 4
7 8 9
12 11 10
13 14 15

输出 #1

26
41

思路

DP即可。

代码

#include<bits/stdc++.h>
using namespace std;
int t,n,a[1005][5],f[5][1005][1005][5][5],f2[105][105][5],d[5][5],op=0,a1h=0,a2h=0,a3h=0;
int main(){
    cin>>t;
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++){
            if(i!=j){
                for(int k=1;k<=3;k++){
                    if(i!=k&&j!=k){
                        d[i][j]=k;
                    }
                }
            }
        }
    }
    while(t--){
        cin>>n;
        a1h=0;
        a2h=0;
        a3h=0;
        for(int i=1;i<=n;i++){
            cin>>a[i][1]>>a[i][2]>>a[i][3];
            a1h+=a[i][1];
            a2h+=a[i][2];
            a3h+=a[i][3];
        }
        if(n<=100){
            for(int i=0;i<=2;i++){
                for(int j=0;j<=n;j++){
                    for(int k=0;k<=j;k++){
                        for(int p=1;p<=3;p++){
                            for(int q=1;q<=3;q++){
                                if(p!=q){
                                    f[i][j][k][p][q]=-1e9-7;
                                }
                            }
                        }
                    }
                }
            }
            for(int i=1;i<=3;i++){
                for(int j=1;j<=3;j++){
                    if(i!=j){
                        f[0][0][0][i][j]=0;
                    }
                }
            }
            for(int i=0;i<=n-1;i++){
                for(int j=0;j<=i;j++){
                    for(int k=0;k<=j;++k){
                        for(int p=1;p<=3;++p){
                            for(int q=1;q<=3;++q){
                                if(p!=q){
                                    f[(i+1)%3][j+1][k+1][p][q]=max(f[(i+1)%3][j+1][k+1][p][q],f[i%3][j][k][p][q]+a[i+1][d[p][q]]-(j+1)-(k+1));
                                    if(k==i){
                                        f[(i+1)%3][j+1][1][p][d[p][q]]=max(f[(i+1)%3][j+1][1][p][d[p][q]],f[i%3][j][k][p][q]+a[i+1][q]-(j+1)-1+i*(i+1)/2);
                                    }
                                    f[(i+1)%3][j+1][1][p][d[p][q]]=max(f[(i+1)%3][j+1][1][p][d[p][q]],f[i%3][j][k][p][q]+a[i+1][q]-(j+1)-1);
                                    if(j==i){
                                        f[(i+1)%3][k+1][1][q][d[p][q]]=max(f[(i+1)%3][k+1][1][q][d[p][q]],f[i%3][j][k][p][q]+a[i+1][p]-(k+1)-1+i*(i+1)/2);
                                    }
                                    f[(i+1)%3][k+1][1][q][d[p][q]]=max(f[(i+1)%3][k+1][1][q][d[p][q]],f[i%3][j][k][p][q]+a[i+1][p]-(k+1)-1);
                                }
                            }
                        }
                    }
                }
                for(int j=0;j<=i;j++){
                    for(int k=0;k<=j;k++){
                        for(int p=1;p<=3;p++){
                            for(int q=1;q<=3;q++){
                                if(p!=q){
                                    f[(i+2)%3][j][k][p][q]=0;
                                }
                            }
                        }
                    }
                }
            }
            op=0;
            for(int i=0;i<=n;i++){
                for(int j=0;j<=i;j++){
                    for(int p=1;p<=3;p++){
                        for(int q=1;q<=3;q++){
                            if(p!=q){
                                if(i==n||j==n){
                                    op=max(op,f[n%3][i][j][p][q]+n*(n+1)/2);
                                }
                                if(i==n&&j==n){
                                    op=max(op,f[n%3][i][j][p][q]+n*(n+1)/2*2);
                                }
                                op=max(op,f[n%3][i][j][p][q]);
                            }
                        }
                    }
                }
            }
            cout<<op<<endl;      
            continue;
        }
        for(int i=0;i<=2;i++){
            for(int j=0;j<=n;j++){
                for(int k=0;k<=j;k++){
                    for(int p=1;p<=3;p++){
                        for(int q=1;q<=3;q++){
                            if(p!=q){
                                f[i][j][k][p][q]=-1e9-7;
                            }
                        }
                    }
                }
            }
        }
        for(int i=1;i<=3;i++){
            for(int j=1;j<=3;j++){
                if(i!=j){
                    f[0][0][0][i][j]=0;
                }
            }
        }
        for(int i=0;i<=n-1;i++){
            for(int j=0;j<=min(i,220+1);j++){
                if(j==221){
                    j=i;
                }
                for(int k=0;k<=j;k++){
                    for(int p=1;p<=3;p++){
                        for(int q=1;q<=3;q++){
                            if(p!=q){
                                f[(i+1)%3][j+1][k+1][p][q]=max(f[(i+1)%3][j+1][k+1][p][q],f[i%3][j][k][p][q]+a[i+1][d[p][q]]-(j+1)-(k+1));
                                if(k==i){
                                    f[(i+1)%3][j+1][1][p][d[p][q]]=max(f[(i+1)%3][j+1][1][p][d[p][q]],f[i%3][j][k][p][q]+a[i+1][q]-(j+1)-1+i*(i+1)/2);
                                }
                                f[(i+1)%3][j+1][1][p][d[p][q]]=max(f[(i+1)%3][j+1][1][p][d[p][q]],f[i%3][j][k][p][q]+a[i+1][q]-(j+1)-1);
                                if(j==i){
                                    f[(i+1)%3][k+1][1][q][d[p][q]]=max(f[(i+1)%3][k+1][1][q][d[p][q]],f[i%3][j][k][p][q]+a[i+1][p]-(k+1)-1+i*(i+1)/2);
                                }
                                f[(i+1)%3][k+1][1][q][d[p][q]]=max(f[(i+1)%3][k+1][1][q][d[p][q]],f[i%3][j][k][p][q]+a[i+1][p]-(k+1)-1);
                            }
                        }
                    }
                }
            }
            for(int j=0;j<=min(i-1,231);j++){
                if(j==231){
                    j=i-1;
                }
                for(int k=0;k<=j;k++){
                    for(int p=1;p<=3;p++){
                        for(int q=1;q<=3;q++){
                            if(p!=q){
                                f[(i+2)%3][j][k][p][q]=0;
                            }
                        }
                    }
                }
            }
        }
        op=0;
        for(int i=0;i<=n;i++){
            for(int j=0;j<=i;j++){
                for(int p=1;p<=3;p++){
                    for(int q=1;q<=3;q++){
                        if(p!=q){
                            if(i==n||j==n){
                                op=max(op,f[n%3][i][j][p][q]+n*(n+1)/2);
                            }
                            if(i==n&&j==n){
                                op=max(op,f[n%3][i][j][p][q]+n*(n+1)/2*2);
                            }
                            op=max(op,f[n%3][i][j][p][q]);
                        }
                    }
                }
            }
        }
        cout<<op<<endl;
    }
    return 0;
}