本文主要是介绍【CF】团队训练赛3 G-Chevonne‘s Necklace 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：Chevonne’s Necklace
标签：动态规划
题目大意
现有一串环形珍珠项链，其上有n个珍珠，现在你要尽可能多地将上面的珍珠取下来。具体规则为：每个珍珠有一个属性c，当你选择取下第i个珍珠时，将会连带取下其顺时针方向的ci-1个珍珠。需要注意的是当此时项链上的珍珠数量不足ci个时，你不能取下第i个珍珠。现在请你输出可以取下的最多珍珠数，以及在此基础上的方案数（规定两个方案不同当且仅当：两个方案选择的珍珠不同，或将选择的珍珠按ci排序后的结果不同）。
输入：第一行一个正整数n(1<=n<=2000)，代表项链上的珍珠数量，第二行n个正整数c1,c2,…,cn(0<=ci<=2000)，代表各个珍珠的属性值。
输出：两个正整数，第一个数代表最多能取下的珍珠数，第二个数代表方案数，答案对998244353取模。
算法分析
- 读完题，正常人都会觉得这是个环形dp，但并非如此。我们先想第一个问题，如何才能知道最多能取下多少个珍珠？如果我们贪心，建一个大根堆，每次取一个当前ci最大的珍珠，是否就是最优策略了呢？并不是。因为这样可能会导致一些ci大的珍珠被它后面的珍珠连带取下，从而使其优势无法发挥出来。
- 只考虑如果尽可能地多取似乎有些难，那我们不如换个角度想：先解决第二个问题，然后就知道第一个问题的答案了。因为如果取1~n个珍珠的方案数都分别求出来了，我们只要从大到小找第一个非零数，也就是第一个有方案的珍珠数，就能知道最多能取多少个了。求方案数，还要取模，那肯定是动态规划没跑了。现在只要考虑状态设计和转移方程。
- 题目里给出了判断两个方案不同的规则，我们不难发现两个方案的区别在于不同的珍珠，而不在选择的顺序。也就是说，对于同样的k个珍珠，你先选哪个后选哪个都无所谓，都是同一种方案。我们很容易发现：既然当前珍珠总数不能超过被选则的ci，那么对于每一种方案，被选择的珍珠的ci之和加起来不可能超过n。而在这个前提下，一定有一种方法使得被选择的珍珠之间不会连带彼此。
- 这一点很好证明。因为被选择的k个珍珠不能覆盖超过n个珍珠，那么此时必然有一个被选择的珍珠满足：取下它不会连带到另外的k-1个珍珠。有了这个结论，本题就类似于一个背包问题变式，给出n个物品，每个物品价值为ci，求价值总和为x(x=1,2,…,n)的方案有多少个。那么我们直接将其定义为dp[j]，不难发现，当ci>=j时，会使得dp[j]+=dp[j-ci]，因为此时对于第i个物品可选可不选。还要特殊考虑ci=0的珍珠，因为它只能被连带而不能被选择。最后因为j不会超过n，所以最终的复杂度为O(n2)。
代码实现
#include <iostream>
using namespace std;
long long dp[2005][2005];
const long long mod=998244353;
int main(){long long i,j,x,a,b,l,r,mid,h,n,m,ans,T;ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;for(i=1;i<=n;i++){dp[i-1][0]=dp[i][0]=1;cin>>x;if(!x){for(j=1;j<=n;j++)dp[i][j]=dp[i-1][j];continue;}for(j=1;j<x;j++)dp[i][j]=dp[i-1][j];for(j=x;j<=n;j++)dp[i][j]=(dp[i-1][j]+dp[i-1][j-x])%mod;}i=n;while(!dp[n][i])i--;cout<<i<<' '<<dp[n][i];return 0;
}
这篇关于【CF】团队训练赛3 G-Chevonne‘s Necklace 题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
