专栏文章

题解：CF1057C Tanya and Colored Candies

TThe_Root
CF1057C题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miot3eg8
此快照首次捕获于
2025/12/03 00:42
3 个月前
此快照最后确认于
2025/12/03 00:42
3 个月前
查看原文
题目传送门

背景

这是本蒟蒻第一次写题解 ，希望 dalaodalao 多多关照🙏

题目描述

有 nn 个糖盒 ， 每个有 r[i] 颗糖，并有 RGBRGB 中的一种颜色 （ 一盒糖颜色相同 ），Tanya 从第 SS 个盒子开吃 ，每个盒子吃一盒糖，并且她希望她吃的每盒糖的数量递增 ，同时满足：
    1. 她不能连续吃的两盒颜色相同
    1. 每移到相邻糖盒须花费1秒，吃糖不费时间
    1. 要吃就吃完
      求吃 kk 盒糖要多久？

思路

这是一道 dpdp 题，考虑 nn 只有50，所以直接 dpdp 。
设计状态 dp[i][j]dp[i][j] 表示时间为i ，当前为j最多能吃多少颗糖 ，对于每盒糖，我们通过三重循环求出答案 列出转移方程 :
如果上一个的颜色和现在的 不一样 ，且现在的比上一个多 ，则有：
dp[i+abs(j−u)][u]=max(dp[i+abs(j−u)][u]，dp[i][j]+r[u])dp[i+abs(j-u)][u]=max(dp[i+abs(j-u)][u]，dp[i][j]+r[u])
所以这个状态是可行的
rr 数组表示每个盒子里有多少糖果 ， abs(j−u)abs(j-u) 表示上一个到这一个的距离，因为移动一个盒子只需1秒 ，所以距离等于时间 。

时间复杂度分析

枚举上一个编号 jj ,当前编号 uu ,时间 ii ，时间复杂度为 O(n4)O(n⁴) ，nn 最大为 5050 ，不会超时 。

代码（含注释）

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;
}
由于是第一次写题解 ，格式有点乱 ，管理员能看下来 ，也是十分辛苦了 ！！！

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...