题解：CF1057C Tanya and Colored Candies
题目传送门
背景
这是本蒟蒻第一次写题解 ，希望
题目描述
有
-
- 她不能连续吃的两盒颜色相同
-
- 每移到相邻糖盒须花费1秒，吃糖不费时间
-
- 要吃就吃完
求吃k 盒糖要多久？思路
这是一道
dp 题，考虑n 只有50，所以直接dp 。
设计状态dp[i][j] 表示时间为i ，当前为j最多能吃多少颗糖 ，对于每盒糖，我们通过三重循环求出答案 列出转移方程 :
如果上一个的颜色和现在的 不一样 ，且现在的比上一个多 ，则有：dp[i+abs(j-u)][u]=max(dp[i+abs(j-u)][u]，dp[i][j]+r[u]) 所以这个状态是可行的
## 时间复杂度分析 枚举上一个编号 $j$ ,当前编号 $u$ ,时间 $i$ ，时间复杂度为 $O(n⁴)$ ，$n$ 最大为 $50$ ，不会超时 。 ### 代码（含注释） ```Cpp #include<bits/stdc++.h> #include<algorithm> using namespace std; #define int long long const int INF=-0x3f3f3f; //将初值设为极小值 int n,s,k,ans; string t; int dp[2550][2550]; //dp数组 int r[2550]; //每个盒子糖果数量 char c[2550]; //每个盒子糖果颜色 signed main(){ int i,j,u; memset(dp,INF,sizeof(dp)); //设初值 cin>>n>>s>>k; for(i=1;i<=n;i++){ cin>>r[i]; } cin>>t; for(i=0;i<n;i++){ c[i+1]=t[i]; //把字符串转为数组（可以直接用scanf("%s",c); } for(i=1;i<=n;i++){ dp[abs(i-s)][i]=r[i]; //设值 } for(i=0;i<=n*n;i++) //枚举时间{ for(j=1;j<=n;j++) //枚举上一个元素{ if(dp[i][j]<=0){ continue; //只处理有值元素 } if(dp[i][j]>=k){ cout<<i; //找到答案输出 return 0; } for(u=1;u<=n;u++) //枚举当前元素{ if(r[u]>r[j]&&c[u]!=c[j]) //判断是否合法{ dp[i+abs(j-u)][u]=max(dp[i+abs(j-u)][u],dp[i][j]+r[u]); //状态转移 } } } } cout<<-1; return 0; } ``` ### 代码（不带注释版） ~~~Cpp #include<bits/stdc++.h> #include<algorithm> using namespace std; #define int long long const int INF=-0x3f3f3f; int n,s,k,ans; string t; int dp[2550][2550]; int r[2550]; char c[2550]; signed main(){ int i,j,u; memset(dp,INF,sizeof(dp)); cin>>n>>s>>k; for(i=1;i<=n;i++){ cin>>r[i]; } cin>>t; for(i=0;i<n;i++){ c[i+1]=t[i]; } for(i=1;i<=n;i++){ dp[abs(i-s)][i]=r[i]; } for(i=0;i<=n*n;i++){ for(j=1;j<=n;j++){ if(dp[i][j]<=0){ continue; } if(dp[i][j]>=k){ cout<<i; return 0; } for(u=1;u<=n;u++){ if(r[u]>r[j]&&c[u]!=c[j]){ dp[i+abs(j-u)][u]=max(dp[i+abs(j-u)][u],dp[i][j]+r[u]); } } } } cout<<-1; return 0; } ~~~ **由于是第一次写题解 ，格式有点乱 ，管理员能看下来 ，也是十分辛苦了 ！！！**
- 要吃就吃完