出题人题解|颗秒

T3_颗秒 题解

特殊性质 $\tt{A:}$

得分型性质。

$s=1$，每秒有三种走法。分别是左转 $1$，不旋转，右转 $1$。也即 $n$ 秒共有 $3^n$ 种不同的旋转方式。由于 $n\le 10$，考虑爆搜，时间复杂度：$O(3^n)$

#include<bits/stdc++.h>
using namespace std;
int n,c,s,ans;
int a[2009],b[2009];
void dfs(int k){
    if(k == n+1){
        int cnt = 0;
        for(int i = 1;i<=n;++i){
            if(a[i] == b[i]){
                cnt++;
            }
        }
        ans = max(ans,cnt);
        return ;
    }
    for(int i = -1;i<=1;++i){
        b[k] = b[k-1]+i;
        if(b[k] == -1) b[k] = c-1;
        if(b[k] == c) b[k] = 0;
        dfs(k+1);
    }
}
void solve(){
    cin>>n>>c>>s;
    ans = 0;
    for(int i = 1;i<=n;++i){
        cin>>a[i];
    }
    dfs(1);
    cout<<ans<<'\n';
}
int main(){
    int t;
    cin>>t;
    while(t--){solve();}
}

---

测试点 $4\sim 10(\tt{AC})$

考虑 $dp$。定义 $dp_i$ 表示考虑前 $i$ 个靶子，且必须击中第 $i$ 秒的靶子的情况下最多能击中的靶子数。

初始状态 $dp_0=0$

注意到 $n\le 2\times 10^3$，考虑 $n^2$ 转移。

定义 $dis(i,j)$ 表示 $i,j$ 之间的距离，计算如下

int dis(int x,int y){
    if(x<=y) swap(x,y);
    return min(x-y,c-(x-y));
}

如果要考虑击中第 $j$ 秒的靶子然后击中第 $i$ 秒的靶子：

• 速度：每秒 $s$ 个单位
• 距离：$dis(a_i,a_j)$
• 时间：$i-j$

显然如果距离 $\le$ 速度 $\times$ 时间，并且第 $j$ 个靶子是可达的，那么可以转移 $dp_i=\max(dp_i,dp_j+1)$。

这个可达是一个坑点，由于击中 $0$ 个靶子也是一种状态，所以 $dp$ 不能赋 $0$ 值。

做完了，答案即为 $max_{i=1}^n dp_i$。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t,n,c,s;
int dp[2009],a[2009];
int dis(int x,int y){
    if(x<=y) swap(x,y);
    return min(x-y,c-(x-y));
}
void solve(){
    cin>>n>>c>>s;
    for(int i = 1;i<=n;++i){
        cin>>a[i];
        dp[i] = -1;
    }
    for(int i = 1;i<=n;++i){
        for(int j = 0;j<i;++j){
            if(dis(a[i],a[j])<=(i-j)*s&&dp[j]!=-1){
                dp[i] = max(dp[i],dp[j]+1);
            }
        }
    }
    int ans = 0;
    for(int i = 1;i<=n;++i){
        ans = max(ans,dp[i]);
    }
    cout<<ans<<'\n';
}
signed main(){
    cin>>t;
    while(t--){
        solve();
    }
}

时间复杂度：$O(tn^2)$