2022 Jinan Site J题总结

首先明确一点，如果某一时刻学习了某个技能，之后这个技能的熟练度掉到了0以下，那么这一时刻不如选择别的技能学习，因此最终答案不会受到“熟练度不能减到0以下”的限制。

先考虑朴素的三维dp，设数组abc分别代表三种技能的贡献，设dpi,j,k代表三种技能上次学习的时间分别为i，j，k时的最大贡献，特别的，i（j，k）=0代表没有学习过。我们在遍历时间轴时，可以先枚举当前时间选择的技能，再枚举上一个时间点选择的技能，比如，当前时间点是i，选择了技能1，上一刻也选择了技能1，那么dpi,j,k可以由dpi-1,j,k+ai-(i-j)-(i-k)转移得到，特别的，如果j=0，就不用-(i-j)这一项，k同理，因为如果还没学习，就不会产生损耗。遍历时间轴是O(n)的，枚举两次时间点需要3*3次，然后再枚举j,k的转移，时间复杂度大概为O(n * 9 * max(abc)^2)=O(9e11),显然不可接受。

考虑优化，注意到max(a,b,c)=1e5,并且如果某个技能间隔了x天没有学习，产生的贡献是负的x方级别的，容易想到对于某个技能，两次学习的间隔不会超过某个阈值，比如，如果一个技能200天没有学习，那么不如在100天时学习一下，得到的贡献明显更大。这样一来，时间复杂度就可以接受了，因为对于当前时间点，j和k各自最多往前枚举200多一点。再考虑空间复杂度，显然我们开不下1000 * 1000 * 1000的数组，但是由上述结论我们可以发现，当枚举时间点到i时，dp1~ i-210,1~ j-210,1~ k-210的值已经完全没有用了，我们可以用类似循环队列的方式优化这些空间，于是，我们只需开大概210 * 210 * 210的空间就足够了。

一些细节问题：

• 初始化dp数组时不能无脑memset，因为T=1e3，会超时，正确做法是初始化下标0~ min(n,210)的dp数组。
• 时限卡得比较紧，尽量不要分成很多个三重循环来写，能用int不要用long long。
• 注意枚举0这一特殊情况，下标为0的dp数组不能被覆盖！

```#include<bits/stdc++.h>
#include<queue>
#include<string.h>
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
//#define int long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define nl tree[n].l
#define nr tree[n].r
#define gcd __gcd
using namespace std;
//#pragma GCC optimize(2)
const int maxn=1e6+50;
const int inf=1e18;
const int mod=1e9+7;
const int INF=2e18;
const double eps=1e-8;
int a[1005],b[1005],c[1005];
int dp[210][210][210];
void solve()
{
    int n;
    cin>>n;
    rep(i,1,n) cin>>a[i]>>b[i]>>c[i];
    int lim=min(205,n);
  rep(i,0,lim)
  {
      rep(j,0,lim)
      {
          rep(k,0,lim) dp[i][j][k]=0;
      }
  }
    dp[1][0][0]=a[1];
    dp[0][1][0]=b[1];
    dp[0][0][1]=c[1];

    rep(i,2,n)
    {
        int st=max(1,i-203);
        int nowi=(i-1)%205+1;
        int lasti=(i-2)%205+1;
        rep(j,0,i-2)
        {
            int nowj=(j-1)%205+1;
            rep(k,0,i-2)
            {
                if(j==k&&j) continue;
                int nowk=(k-1)%205+1;
                 if(j==0&&k==0)
                {
                dp[nowi][nowj][nowk]=max(dp[nowi][nowj][nowk],a[i]+dp[lasti][nowj][nowk]);
                dp[nowj][nowi][nowk]=max(dp[nowj][nowi][nowk],b[i]+dp[nowj][lasti][nowk]);
                dp[nowj][nowk][nowi]=max(dp[nowj][nowk][nowi],c[i]+dp[nowj][nowk][lasti]);
                }
                else if(j==0)
                {
                     dp[nowi][nowj][nowk]=max(dp[nowi][nowj][nowk],a[i]+dp[lasti][nowj][nowk]-(i-k));
                     dp[nowj][nowi][nowk]=max(dp[nowj][nowi][nowk],b[i]+dp[nowj][lasti][nowk]-(i-k));
                     dp[nowj][nowk][nowi]=max(dp[nowj][nowk][nowi],c[i]+dp[nowj][nowk][lasti]-(i-k));
                }
                else if(k==0)
                {
                     dp[nowi][nowj][nowk]=max(dp[nowi][nowj][nowk],a[i]+dp[lasti][nowj][nowk]-(i-j));
                     dp[nowj][nowi][nowk]=max(dp[nowj][nowi][nowk],b[i]+dp[nowj][lasti][nowk]-(i-j));
                     dp[nowj][nowk][nowi]=max(dp[nowj][nowk][nowi],c[i]+dp[nowj][nowk][lasti]-(i-j));
                }
                else
                {
                     dp[nowi][nowj][nowk]=max(dp[nowi][nowj][nowk],a[i]+dp[lasti][nowj][nowk]-(i-j)-(i-k));
                     dp[nowj][nowi][nowk]=max(dp[nowj][nowi][nowk],b[i]+dp[nowj][lasti][nowk]-(i-j)-(i-k));
                     dp[nowj][nowk][nowi]=max(dp[nowj][nowk][nowi],c[i]+dp[nowj][nowk][lasti]-(i-j)-(i-k));
                }
                  if(k==0)
                {
                    dp[nowi][lasti][nowk]=max(dp[nowi][lasti][nowk],a[i]+dp[nowj][lasti][nowk]-1);
                    dp[nowi][nowk][lasti]=max(dp[nowi][nowk][lasti],a[i]+dp[nowj][nowk][lasti]-1);
                    dp[lasti][nowi][nowk]=max(dp[lasti][nowi][nowk],b[i]+dp[lasti][nowj][nowk]-1);
                    dp[nowk][nowi][lasti]=max(dp[nowk][nowi][lasti],b[i]+dp[nowk][nowj][lasti]-1);
                    dp[lasti][nowk][nowi]=max(dp[lasti][nowk][nowi],c[i]+dp[lasti][nowk][nowj]-1);
                    dp[nowk][lasti][nowi]=max(dp[nowk][lasti][nowi],c[i]+dp[nowk][lasti][nowj]-1);
                    k=st-1;

                }
                else
                {
                    dp[nowi][lasti][nowk]=max(dp[nowi][lasti][nowk],a[i]+dp[nowj][lasti][nowk]-1-(i-k));
                    dp[nowi][nowk][lasti]=max(dp[nowi][nowk][lasti],a[i]+dp[nowj][nowk][lasti]-1-(i-k));
                    dp[lasti][nowi][nowk]=max(dp[lasti][nowi][nowk],b[i]+dp[lasti][nowj][nowk]-1-(i-k));
                    dp[nowk][nowi][lasti]=max(dp[nowk][nowi][lasti],b[i]+dp[nowk][nowj][lasti]-1-(i-k));
                    dp[lasti][nowk][nowi]=max(dp[lasti][nowk][nowi],c[i]+dp[lasti][nowk][nowj]-1-(i-k));
                    dp[nowk][lasti][nowi]=max(dp[nowk][lasti][nowi],c[i]+dp[nowk][lasti][nowj]-1-(i-k));
                }
               

            }
            if(j==0) j=st-1;
        }
     
    }
    int ans=0;
    int nown=(n-1)%205+1;
    rep(i,0,lim)
    {
        rep(j,0,lim)
        {
            if(i==j&&i) continue;
            ans=max({ans,dp[nown][i][j],dp[i][j][nown],dp[i][nown][j]});
        }
    }
    cout<<ans<<'\n';
}
signed main()
{
   ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
   int __=1;
   cin>>__;
  while(__--)
  {
       solve();

  }
    return 0;
}