listview air mysql默认密码 matlab根号怎么打出来 hbase集群搭建 solr索引 oracle创建唯一索引 python随机数 python开发工具 python中set的用法 python读取字典 java字符串查找 java开发者 java的random java命令 java获取 linux系统教程 linux下载安装 服务器操作系统下载 冬青鼠 python封装 raid0教程 网络克隆 临时会话 dnf武极刷图加点 为什么英雄联盟无法连接服务器 maya2016教程 spss22安装教程 python爬虫代码 文章查重软件 圆角矩形工具改变弧度 挑战程序设计竞赛 jsp源码 omg小北 ipad怎么清理内存垃圾 数据库编程软件 cdr裁剪工具怎么用 小米自动开关机 iosps腹肌 脚本模板
当前位置: 首页 > 学习教程  > 编程语言

DP 补2021.01.11

2021/1/13 19:23:56 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

一.最长公共子序列 1. 题面&#xff1a; 2. 题解&#xff1a; 如果s1的第i个字符和s2的第j个字符一样&#xff0c;dp[i][j]dp[i-1][j-1]1&#xff0c;如果不同&#xff0c;就等于max(dp[i-1][j],dp[i][j-1]&#xff09; 3. ac代码&#xff1a; #include<stdio.h> #in…

一.最长公共子序列

1. 题面:

在这里插入图片描述

2. 题解:

如果s1的第i个字符和s2的第j个字符一样,dp[i][j]=dp[i-1][j-1]+1,如果不同,就等于max(dp[i-1][j],dp[i][j-1])

3. ac代码:

#include<stdio.h>
#include<bits/stdc++.h>
#include<iostream>
#include<string.h>
#include<stdlib.h>
//long long int dp2[400000],dp1[400000],a[400000];
using namespace std;

int main(){
	char s1[200],s2[200];
	int i,j;
	int n1,n2;
	int dp[200][200];
	while(~scanf("%s%s",s1+1,s2+1)){
		n1=strlen(s1+1);
		n2=strlen(s2+1);
		memset(dp,0,sizeof(dp));
		for(i=1;i<=n1;i++){
			for(j=1;j<=n2;j++){
				if(s1[i]==s2[j]){
					dp[i][j]=dp[i-1][j-1]+1;
				}else{
					dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
				}
			}
		}
		cout<<dp[n1][n2]<<endl;
	}


}

二.最大子矩阵


参考1(不完全正确)
参考2

1. 题面:

在这里插入图片描述

2. 题解:

看参考一

3. ac代码:

相较于参考1只是这部分有改动:

	               if(sum>0)
					 sum+=b[k];
					else
					  sum=b[k];//可能矩阵全负 
					//sum=max(b[k],sum+b[k])

原来的:

                     sum+=b[k];
					if(sum<0)
					 sum=b[k];//可能矩阵全负 

不太懂原来的哪些情况会卡,求指教

#include<stdio.h>
#include<bits/stdc++.h>
#include<iostream>
#include<string.h>
#include<stdlib.h>
//long long int dp2[400000],dp1[400000],a[400000];
using namespace std;
typedef long long ll;

int main(){
	int n;
	int a[105][105];
	int i,j,k;
	int b[105];
	while(cin>>n){
		for(i=1;i<=n;i++){
			for(j=1;j<=n;j++){
				cin>>a[i][j];
			}
		}
		
		int maxn=-9999999;
		for(i=1;i<=n;i++){
	     	memset(b,0,sizeof(b));//每次开始行变化时都需要初始化b,b表示的是从i行到j行的最大子矩阵。 
			for(j=i;j<=n;j++){
				int sum=0;
				for(k=1;k<=n;k++){
					b[k]+=a[j][k];
					
					if(sum>0)
					 sum+=b[k];
					else
					  sum=b[k];//可能矩阵全负 
					if(sum>maxn)
					maxn=sum;
				}
				
			}
		}
		cout<<maxn<<endl;
	}
}
//101010101000000111111

还有最常规的方法,是O(n^4)
详见该文

三.分苹果

1. 题面:

在这里插入图片描述

2. 题解:

1.递归:

设f(m,n) 为m个苹果,n个盘子的放法数目,则先对n作讨论,
当n>m:必定有n-m个盘子永远空着,去掉它们对摆放苹果方法数目不产生影响。即if(n>m) f(m,n) = f(m,m)  
当n<=m:不同的放法可以分成两类:
1、有至少一个盘子空着,即相当于f(m,n) = f(m,n-1);
2、所有盘子都有苹果,相当于可以从每个盘子中拿掉一个苹果,不影响不同放法的数目,即f(m,n) = f(m-n,n).
而总的放苹果的放法数目等于两者的和,即 f(m,n) =f(m,n-1)+f(m-n,n)
递归出口条件说明:
当n=1时,所有苹果都必须放在一个盘子里,所以返回1;
当没有苹果可放时,定义为1种放法;
递归的两条路,第一条n会逐渐减少,终会到达出口n=1;
第二条m会逐渐减少,因为n>m时,我们会return f(m,m) 所以终会到达出口m=0.

2.dp:
新建一个动态规划表 dp;dp[i][j] 表示 i 个盘子放 j 个苹果的方法数。
则 当 i > j 时,dp[i][j] = dp[i - (i - j)][j] = dp[j][j]
当 i <= j 时,dp[i][j] = dp[i - 1][j] + dp[i][j - i];
最后dp[n][m] 就是所求。

3. ac代码:

#include<stdio.h>
#include<bits/stdc++.h>
#include<iostream>
#include<string.h>
#include<stdlib.h>
//long long int dp2[400000],dp1[400000],a[400000];
using namespace std;
typedef long long ll;
int dg(int n,int m){
	if(n==0||m==1)
	 return 1;
	if(n<m)
	 return dg(n,n);
	return dg(n-m,m)+dg(n,m-1);
}
int main(){
	int n,m,t,c;
	while(cin>>t){
		while(t--){
			cin>>n>>m;
			c=dg(n,m);
			cout<<c<<endl;
		}
	}
	
}


本文链接: http://www.dtmao.cc/news_show_600052.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?