首页 > 其他分享 >Living-Dream 系列笔记 第50期

Living-Dream 系列笔记 第50期

时间:2024-03-16 19:11:58浏览次数:23  
标签:Living min int sum 50 times num Dream dp

T1

构思分讨。

很自然地,我们令 \(dp_{i,j}\) 表示 \([i,j]\) 的初始字母方案数。

但是这个状态信息过少,不足以解决此问题。

于是我们增加状态维度,令 \(dp_{i,j,0/1/2/3}\) 表示 \([i,j]\) 是否能由 W/I/N/D 演变而来。

答案即为 \(dp_{1,n,0} \mid \mid dp_{1,n,1} \mid \mid dp_{1,n,2} \mid \mid dp_{1,n,3}\)。

显然有初始状态 \(dp_{i,j,0/1/2/3} = 1\),因为无论哪个字母,它本身即可演变为它。其余为 \(\infty\)。

关于转移,我们考虑枚举中转点的套路去做。

对于区间 \([i,j]\),我们确定中转点 \(k\) 后,仅需枚举 \(c1,c2,c\),并检查 \(dp_{i,k,c1}=dp_{k+1,j,c2}=dp_{i,j,c}=1\),且 \(c1,c2\) 能演变为 \(c\) 即可。

code
#include<bits/stdc++.h>
using namespace std;

const int N=2e2+5;
string t;
int n,a[4];
int num[N],ok[4][4][4];
int dp[N][N][4];

int main(){
	for(int i=0;i<4;i++) cin>>a[i];
	num['W']=0,num['I']=1,num['N']=2,num['G']=3;
	for(int i=0;i<4;i++){
		for(int j=1;j<=a[i];j++){
			char c1,c2; cin>>c1>>c2;
			ok[i][num[c1]][num[c2]]=1;
		}
	}
	cin>>t,n=t.size(),t='#'+t;
	for(int i=1;i<=n;i++) dp[i][i][num[t[i]]]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j+i-1<=n;j++){
			int s=j,e=i+j-1;
			for(int k=s;k<e;k++)
				for(int c=0;c<4;c++)
					for(int c1=0;c1<4;c1++)
						for(int c2=0;c2<4;c2++)
							dp[s][e][c]|=(dp[s][k][c1]&&dp[k+1][e][c2]&&ok[c][c1][c2]); 
		}
	}
	bool f=0;
	if(dp[1][n][0]) cout<<'W',f=1;
	if(dp[1][n][1]) cout<<'I',f=1;
	if(dp[1][n][2]) cout<<'N',f=1;
	if(dp[1][n][3]) cout<<'G',f=1;
	if(!f) cout<<"The name is wrong!";
	return 0;
}

T2

构思分讨 \(\times \ 2\)。

令 \(dp_{i,j}\) 表示关掉 \([i,j]\) 内所有灯的最少功率。

但是,我们在关 \([i,j]\) 时,最后停在那个点将会影响到答案。

进一步分析,我们发现,关 \([i,j]\) 时,有且仅有可能停在 \(i,j\) 两点上。

这是因为,我们如果停在了满足 \(i<p<j\) 的点 \(p\),则我们会走一遍 \(i \to j \to p\) 或 \(j \to i \to p\),这一定不会比只走 \(i \to j\) 或 \(j \to i\) 更优。

于是我们令 \(dp_{i,j,0/1}\) 表示关掉 \([i,j]\) 且停在 \(i/j\) 的最小功率。

答案即为 \(\min(dp_{1,n,0},dp_{1,n,1})\)。

关于初始状态,因为每次出发时总会将 \(c\) 关掉,

因此有初始状态 \(dp_{i,i,0/1}=\lvert x_i-x_c \rvert + sum_n-w_c\),其余为 \(\infty\)。

其中 \(x_i\) 表示位置,\(w_i\) 表示功率,\(sum_i\) 表示 \(w_i\) 的前缀和。

接下来考虑转移。

这题肯定不能用枚举中转点套路,因为无法确定终止位置。

于是用端点转移套路,具体地:

  • 对于 \(dp_{i,j,0}\),可以 \(i+1 \to j \to i\) 或 \(j \to i+1 \to i\)。

    因此有转移

\[dp_{i,j,0}=\min(dp_{i+1,j,0}+(x_{i+1}-x_i) \times (sum_n-(sum_j-sum_i)),dp_{i+1,j,1}+(x_j-x_i) \times (sum_n-(sum_j-sum_i))) \]

  • 对于 \(dp_{i,j,1}\),可以 \(i \to j-1 \to j\) 或 \(j-1 \to i \to j\)。

    因此有转移

\[dp_{i,j,1}=min(dp_{i,j-1,0}+(x_j-x_i) \times (sum_n-(sum_{j-1}-sum_{i-1})),dp_{i,j-1,1}+(x_j-x_{j-1}) \times (sum_n-sum_{j-1}+sum_{i-1})) \]

直接做就完了。

code
#include<bits/stdc++.h>
using namespace std;

int n,c;
int x[53],w[53];
int sum[53];
int dp[53][53][2];

int main(){
	cin>>n>>c;
	for(int i=1;i<=n;i++) cin>>x[i]>>w[i],sum[i]=sum[i-1]+w[i];
	memset(dp,0x3f,sizeof(dp));
	for(int i=1;i<=n;i++) dp[i][i][0]=dp[i][i][1]=abs(x[i]-x[c])*(sum[n]-w[c]);
	for(int i=2;i<=n;i++){
		for(int j=1;j+i-1<=n;j++){
			int s=j,e=j+i-1;
			dp[s][e][0]=min(dp[s+1][e][0]+(x[s+1]-x[s])*(sum[n]-sum[e]+sum[s]),dp[s+1][e][1]+(x[e]-x[s])*(sum[n]-sum[e]+sum[s]));
			dp[s][e][1]=min(dp[s][e-1][0]+(x[e]-x[s])*(sum[n]-sum[e-1]+sum[s-1]),dp[s][e-1][1]+(x[e]-x[e-1])*(sum[n]-sum[e-1]+sum[s-1]));
		}
	}
	cout<<min(dp[1][n][0],dp[1][n][1]);
	return 0;
}

作业 T1

TJ

作业 T2

构思分讨 \(\times \ 3\)。

法一:

令 \(dp_{i,j,0/1}\) 表示将 \([i,j]\) 变为颜色均为 \(c_i/c_j\) 的连通块的最小步数。

答案即为 \(\min(dp_{1,n,0},dp_{1,n,1})\)。

显然有初始状态 \(dp_{i,i,0/1}\)=0,其余为 \(\infty\)。

从状态易知,此题应用端点转移法进行转移。

于是有转移:

\[\begin{cases} dp_{i,j,0}=\min(dp_{i,j,0},dp_{i+1,j,0}+(c_i \neq c_{i+1}))\\ dp_{i,j,0}=\min(dp_{i,j,0},dp_{i+1,j,1}+(c_i \neq c_j))\\ dp_{i,j,1}=\min(dp_{i,j,1},dp_{i,j-1,0}+(c_j \neq c_i))\\ dp_{i,j,1}=\min(dp_{i,j,1},dp_{i,j-1,1}+(c_j \neq c_{j-1})) \end{cases} \]

法一 code
#include<bits/stdc++.h>
using namespace std;

const int N=5e3+5;
int n,c[N];
int dp[N][N][2];

int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>c[i];
	memset(dp,0x3f,sizeof(dp));
	for(int i=1;i<=n;i++) dp[i][i][0]=dp[i][i][1]=0;
	for(int i=2;i<=n;i++){
		for(int j=1;j+i-1<=n;j++){
			int s=j,e=j+i-1;
			dp[s][e][0]=min(dp[s][e][0],dp[s+1][e][0]+(c[s]!=c[s+1]));
			dp[s][e][0]=min(dp[s][e][0],dp[s+1][e][1]+(c[s]!=c[e]));
			dp[s][e][1]=min(dp[s][e][1],dp[s][e-1][0]+(c[e]!=c[s]));
			dp[s][e][1]=min(dp[s][e][1],dp[s][e-1][1]+(c[e]!=c[e-1]));
		}
	}
	cout<<min(dp[1][n][0],dp[1][n][1]);
	return 0;
}

法二:

先预处理,将所有相同颜色全部合并到一起,组成一个色块。

接着令 \(dp_{i,j}\) 表示将 \([i,j]\) 变为一个连通块的最小步数。

答案即为 \(dp_{1,tot}\),\(tot\) 表示色块个数。

显然有初始状态 \(dp_{i,i}\)=0,其余为 \(\infty\)。

仍然采用端点转移法进行转移。

于是有转移:

\[\begin{cases} dp_{i,j}=\min(dp_{i,j},dp_{i+1,j-1}+1)(cc_i=cc_j)\\ dp_{i,j}=\min(dp_{i,j-1}+1,dp_{i+1,j}+1)(cc_i \neq cc_j) \end{cases} \]

其中 \(cc_i\) 表示第 \(i\) 个色块的颜色。

法二 code
#include<bits/stdc++.h>
using namespace std;

const int N=5e3+5;
int n,tot,pre;
int c[N],cc[N];
int dp[N][N];

int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>c[i];
	for(int i=1;i<=n;i++){
		if(c[i]!=pre) cc[++tot]=c[i]; pre=c[i];
	}
	memset(dp,0x3f,sizeof(dp));
	for(int i=1;i<=tot;i++) dp[i][i]=0;
	for(int i=2;i<=tot;i++){
		for(int j=1;j+i-1<=tot;j++){
			int s=j,e=j+i-1;
			if(cc[s]==cc[e]) dp[s][e]=min(dp[s][e],dp[s+1][e-1]+1);
			else dp[s][e]=min(dp[s][e-1]+1,dp[s+1][e]+1);
		}
	}
	cout<<dp[1][tot];
	return 0;
}

标签:Living,min,int,sum,50,times,num,Dream,dp
From: https://www.cnblogs.com/XOF-0-0/p/18077446

相关文章

  • lc2250 统计包含每个点的矩形数目
    有n个矩形,第i个矩形左下角在(0,0)处,右上角在(l[i],h[i])。另给出m个点(x[i],y[i]),问有多少个矩形覆盖了这个点,点在边上也算是覆盖。1<=n,m<=5e4;1<=l[i],h[i]<=1e9;1<=h[i],y[i]<=100;所有矩形互不相同,所有查询点互不相同。二维偏序统计问题,可以离线处理,先对其中一维排序,将......
  • RX 6750 GRE 10GB和rtx 4080对比 评测
    RX6750GRE10GB基于RDNA2架构Navi22核心,晶体管数为172亿,拥有36组计算单元共计2304个流处理器,36个光追单元;加速频率2450MHz,TGP功耗158W,TBP功耗为170W;无限缓存80MB,采用GDDR6显存,显存位宽160-bit;主要用于1080p及1440p级别游戏市场。选RX6750GRE10GB还是rtx4080这些点很......
  • Ultra 9 185H和i7 12650h选哪个 酷睿Ultra9185H和i712650h对比
    i712650H采用Intel7工艺6大核4小核设计,拥有8核心12线程,三级缓存高达24MB选Ultra9185H还是i712650h这些点很重要看过你就懂了http://www.adiannao.cn/dyUltra9185H处理器是16核心,22线程,Ultra9185H处理器具有6个性能核心,8个效能核心,2个低功耗核心,超大24MB的三级......
  • 酷睿Ultra 9 185h和i5-13500H选哪个好?参数性能区别对比
    i513500h采用10纳米制作工艺最高睿频4.7GHz十二核心十六线程三级缓存18MB热设计功耗(TDP)45W支持最大内存64GB内存类型DDR43200MHzDDR55200MHz集成显卡IntelIrisXeGraphics选Ultra9185h还是i5-13500H这些点很重要看过你就懂了http://www.adiannao.c......
  • 代码随想录算法训练营第十一天| 20. 有效的括号 1047. 删除字符串中的所有相邻重复
    20.有效的括号https://leetcode.cn/problems/valid-parentheses/description/publicbooleanisValid(Strings){if(s==null)returntrue;Stack<Character>stack=newStack<>();for(inti=0;i<s.length();i++){......
  • NEW CONCEPT ENGLISH 41 - 50
    NEWCONCEPTENGLISH41-50Lesson41 Penny'sbagKeywordsandexpressionscheese n. 乳酪,干酪bread n. 面包soap n. 肥皂chocolate n. 巧克力sugar n. 糖coffee n. 咖啡tea n. 茶tobacco n. 烟草,烟丝LanguagepointsIsthatbagheavy,Penny......
  • 代码随想录 第21天 | ● 530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ●
    leetcode:530.二叉搜索树的最小绝对差-力扣(LeetCode)思路:判断最小绝对差,肯定用中序遍历,双指针一前一后依次判断。classSolution{intresult=Integer.MAX_VALUE;TreeNodepre=null;publicintgetMinimumDifference(TreeNoderoot){if(root==......
  • 洛谷题解 - B3850 [GESP202306 四级] 幸运数
    目录题目描述输入格式输出格式样例#1样例输入#1样例输出#1代码题目描述小明发明了一种“幸运数”。一个正整数,其偶数位不变(个位为第111位,十位为第......
  • 计讯物联防水型loRa采集终端TG501-B6-8助攻智慧窨井盖解决方案,守护人们足下安全
    政策背景住房和城乡建设部等6部门联合发布《关于加强窨井盖安全管理的指导意见》,意见指出:到2025年年底前,窨井盖安全管理机制进一步完善,信息化、智能化管理水平明显加强,事故风险监测预警能力和应急处置水平显著提升,窨井盖安全事故明显减少。  来源于住房和城乡建设部窨井盖......
  • 维修住友注塑机 Sumitomo SE50D 工业液晶屏 SE50S工业电脑显示屏
    Sumitomo(SHI)Demag的NC5plus控制器是一款易于使用的控制器,可帮助成型商实现卓越的注塑成型精度。该控制器作为用户和注塑机之间的通信接口发挥着关键作用。只有通过控制才能访问机器的全部性能属性,从而以各种方式帮助最大限度地提高生产效率。NC5+优点易于使用并快速......