【寒假训练/Java】递推专题
文章目录
题目链接
递推专题-牛客链接
比赛密码:202301272000
题目列表
快输
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
out.flush();
}
static class FastReader{
BufferedReader br;
StringTokenizer st;
String tmp;
public FastReader() {
br=new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while(st==null||!st.hasMoreElements()) {
try {
st=new StringTokenizer(br.readLine());
}catch(IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong(){return Long.parseLong(next());}
String nextLine() {
String str="";
try {
str=br.readLine();
}catch(IOException e) {
e.printStackTrace();
}
return str;
}
boolean hasNext(){
if(st!=null&&st.hasMoreTokens())return true;
try {
tmp=br.readLine();
st=new StringTokenizer(tmp);
}catch(IOException e) {
return false;
}
return true;
}
}
static PrintWriter out=new PrintWriter(
new BufferedWriter(new OutputStreamWriter(System.out)));
static FastReader sc=new FastReader();
}
A - 小乐乐走台阶
static int[] dp;
public static void main(String[] args) {
int n=sc.nextInt();
dp=new int[n+1];
dp[1]=1;
dp[2]=2;
for(int i=3;i<=n;i++){
dp[i]=dp[i-1]+dp[i-2];
}
out.println(dp[n]);
out.flush();
}
B - 滑雪(DFS)
深搜遍历得到所有以当前点为起始的最长滑坡的长度
static int n,m;//区域大小
static int[][] dp,mp;//从当前点开始的最长滑坡,地图高度
static int[][] dir={{1,0},{-1,0},{0,-1},{0,1}};//搜索方向
public static void main(String[] args) {
n=sc.nextInt();
m=sc.nextInt();
dp=new int[n+1][m+1];
mp=new int[n+1][m+1];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
mp[i][j]=sc.nextInt();
int s=0;//遍历找最大值
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
s=Math.max(find(i,j), s);
out.println(s);
out.flush();
}
//找出从该点开始能进行的最大次数
public static int find(int x,int y){
if(dp[x][y]!=0) return dp[x][y];
int t=1,nx,ny;
//从四个方向搜索最长滑坡
for(int i=0;i<4;i++) {
nx=x+dir[i][0];
ny=y+dir[i][1];
//若超出临界范围 或者不满足 下一个点的高度小于当前点的高度 这个条件,需要跳过
if(nx<=0||nx>n||ny<=0||ny>m||mp[x][y]<=mp[nx][ny]) continue;
t=Math.max(find(nx,ny)+1,t);
}
dp[x][y]=t;
return t;
}
C - [NOIP2005]采药(01背包)
public static void main(String[] args) {
int T=sc.nextInt(),M=sc.nextInt();//采药总时间(容量),草药数(数量)
//dp:当前时间可以采到的草药的最大价值,t:采药时间,w:草药价值
int[] dp=new int[T+1],t=new int[M+1],w=new int[M+1];
for(int i=1;i<=M;i++){
t[i]=sc.nextInt();
w[i]=sc.nextInt();
}
for(int i=1;i<=M;i++){
for(int j=T;j>=t[i];j--){
dp[j]=Math.max(dp[j],dp[j-t[i]]+w[i]);
}
}
out.println(dp[T]);
out.flush();
}
D - [NOIP2002]过河卒
dp数组表示从(0,0)点出发,到达该点的路径的条数;
将对方马的坐标及其控制点标记为特殊值。在初始化时,第0行和第0列起始值均为1,倘若遇到某一点为-1,即该点为控制点,这个点和之后的所有点均需标记为-1,表示不可达;
//马的八个控制点
static int[][] dir={{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1}};
public static void main(String[] args) {
//B点的坐标(n,m),对方马的坐标(X,Y)以及临时坐标
int n=sc.nextInt(),m=sc.nextInt(),X=sc.nextInt(),Y=sc.nextInt(),nx,ny;
//结果可能爆int
long[][] dp=new long[n+1][m+1];
//对方马的控制点标记为-1
dp[X][Y]=-1;
for(int i=0;i<8;i++){
nx=X+dir[i][0];
ny=Y+dir[i][1];
if(nx<0||nx>n||ny<0||ny>m)continue;
dp[nx][ny]=-1;
}
//经测试,不会存在出发点是对方马的控制点的情况,这里写上表示逻辑完整
if(dp[0][0]==-1)out.println(0);
else{
//初始化:第0行和第0列起始值均为1,倘若遇到某一点为-1,即该点为控制点,这个点和之后的所有点均需标记为-1,表示不可达
int f=0;
for(int i=1;i<=n;i++){
if(f==0&&dp[i][0]==-1)f=-2;
else dp[i][0]=1+f;
}
f=0;
for(int i=1;i<=m;i++){
if(f==0&&dp[0][i]==-1)f=-2;
else dp[0][i]=1+f;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
//控制点跳过
if(dp[i][j]<0)continue;
//到达该点有两条路:从上边点或者从左边点
dp[i][j]=dp[i-1][j]+dp[i][j-1];
//dp数组中控制点的值为-1,所以要+1变为0
if(dp[i-1][j]<0)dp[i][j]++;
if(dp[i][j-1]<0)dp[i][j]++;
}
}
out.println(dp[n][m]);
}
out.flush();
}
E - [NOIP2006]金明的预算方案(01背包)
01背包
将只考虑买不买当前物品,转化为:①只买主件
②买主件&第一个附件
③买主件&第二个附件
④买主件&第所有附件(最多两个附件)
public static void main(String[] args) {
int N=sc.nextInt(),m=sc.nextInt();//总钱数,希望购买物品的个数
int v,p,q;//价格,重要度,主件0 or 附件所属主件的编号>0
/**
* dp:不超过当前钱数的物品的价格与重要度乘积的总和的最大值
* c:价格
* w:物品的价格与重要度乘积
* 二维数组的第二维表示主件0 or 附件编号>0
*/
int[] dp=new int[N+1],c[]=new int[m+1][3],w[]=new int[m+1][3];
for(int i=1;i<=m;i++){
v=sc.nextInt();p=sc.nextInt();q=sc.nextInt();
if(q==0){//主件
c[i][0]=v;
w[i][0]=v*p;
}else{
if(c[q][1]==0){//第一个附件
c[q][1]=v;
w[q][1]=v*p;
}else{//第二个附件
c[q][2]=v;
w[q][2]=v*p;
}
}
}
//01背包
for(int i=1;i<=m;i++){
for(int j=N;j>=1;j--){
int s1=0,s2=0;
//只买主件
if(j>=c[i][0])
dp[j]=Math.max(dp[j],dp[j-c[i][0]]+w[i][0]);
//买主件&第一个附件
s1=c[i][0]+c[i][1];
s2=w[i][0]+w[i][1];
if(j>=s1)
dp[j]=Math.max(dp[j],dp[j-s1]+s2);
//买主件&第二个附件
s1=c[i][0]+c[i][2];
s2=w[i][0]+w[i][2];
if(j>=s1)
dp[j]=Math.max(dp[j],dp[j-s1]+s2);
//买主件&第所有附件
s1=c[i][0]+c[i][1]+c[i][2];
s2=w[i][0]+w[i][1]+w[i][2];
if(j>=s1)
dp[j]=Math.max(dp[j],dp[j-s1]+s2);
}
}
out.println(dp[N]);
out.flush();
}
F - [NOIP2006]开心的金明(01背包)
public static void main(String[] args) {
int N=sc.nextInt(),m=sc.nextInt();//总钱数,希望购买物品的个数
int v,p;//价格,重要度
/**
* dp:不超过当前钱数的物品的价格与重要度乘积的总和的最大值
* c:价格
* w:物品的价格与重要度乘积
*/
int[] dp=new int[N+1],c=new int[m+1],w=new int[m+1];
for(int i=1;i<=m;i++){
v=sc.nextInt();p=sc.nextInt();
c[i]=v;
w[i]=v*p;
}
//01背包
for(int i=1;i<=m;i++){
for(int j=N;j>=c[i];j--){
dp[j]=Math.max(dp[j],dp[j-c[i]]+w[i]);
}
}
out.println(dp[N]);
out.flush();
}
G - 石子合并(区间DP)
public static void main(String[] args) {
//沙子的堆数
int n=sc.nextInt(),MAXN=(int)1e9+7;
//dp:将第i-j堆沙子合并的最小代价
int[] dp[]=new int[n+1][n+1],s=new int[n+1];
for(int i=0;i<=n;i++)Arrays.fill(dp[i],MAXN);
//前缀和
for(int i=1;i<=n;i++) {
s[i]=s[i-1]+sc.nextInt();
}
for(int j=1;j<=n;j++) {//区间长度以及区间右端点
for(int i=j;i>=1;i--){//1~j
if(j==i)dp[i][j]=0;
for(int k=i;k<j;k++){
//第i-j堆沙子被分成两部分,这两部分合并需要加上代价 - 第i-j堆沙子数量之和
dp[i][j]=Math.min(dp[i][j],dp[i][k]+dp[k+1][j]+s[j]-s[i-1]);
}
}
}
out.println(dp[1][n]);
out.flush();
}
H - 没有上司的舞会(DFS)
构建一个职员类,其中维护一个list存储与其互斥的职员;
二维dp数组求最大快乐值:
该职员来:其互斥职员只能不来;
该职员不来:其互斥职员可以来 or 不来;
第二维保存该职员来或不来的状态
递归过程利用深搜实现:
最终返回一条使快乐值最大的子树
import java.io.*;
import java.util.*;
//职员类
class node{
int length;
List<Integer> ls;
public node() {
ls=new ArrayList<>();
length=0;
}
public void ad(int x){
ls.add(x);
length++;
}
public int gt(int x){
return ls.get(x);
}
}
public class Main {
/**
* Hi:快乐指数
* f[i][0]:i不来的情况下以i为根节点的子树的最大快乐值
* f[i][1]:i来的情况下以i为根节点的子树的最大快乐值
* n:总人数
*/
static node[] tree;
static int[] Hi,vis,f[];
static int n,l,k;
public static void main(String[] args) {
n=sc.nextInt();
Hi=new int[n+1];
vis=new int[n+1];
tree=new node[n+1];
f=new int[n+1][2];
for(int i=1;i<=n;i++){
Hi[i]=sc.nextInt();
tree[i]=new node();
}
for(int i=1;i<n;i++){
l=sc.nextInt();
k=sc.nextInt();
tree[l].ad(k);
tree[k].ad(l);
}//最后一行输入0,0 代码中不必体现,否则RE:根据测试,某些样例不含此输入
dfs(1);//从根节点找子树
//每一个节点都有两条分支:来或不来,最终结果为二者最大值
out.println(Math.max(f[1][0],f[1][1]));
out.flush();
}
public static void dfs(int x){
vis[x]=1;
f[x][0]=0;
f[x][1]=Hi[x];
for(int i=0;i<tree[x].length;i++){
int son=tree[x].gt(i);
if(vis[son]!=0)continue;
dfs(son);
//x没有来,son可以来or不来
f[x][0]+=Math.max(f[son][0],f[son][1]);
//x来了,son只能不来
f[x][1]+=f[son][0];
}
}
static class FastReader{
BufferedReader br;
StringTokenizer st;
String tmp;
public FastReader() {
br=new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while(st==null||!st.hasMoreElements()) {
try {
st=new StringTokenizer(br.readLine());
}catch(IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong(){return Long.parseLong(next());}
String nextLine() {
String str="";
try {
str=br.readLine();
}catch(IOException e) {
e.printStackTrace();
}
return str;
}
boolean hasNext(){
if(st!=null&&st.hasMoreTokens())return true;
try {
tmp=br.readLine();
st=new StringTokenizer(tmp);
}catch(IOException e) {
return false;
}
return true;
}
}
static PrintWriter out=new PrintWriter(
new BufferedWriter(new OutputStreamWriter(System.out)));
static FastReader sc=new FastReader();
}
I - [NOIP2004]合唱队形(最长上升子序列LIS)
求最少需要几位同学出列,转为求最长上升子序列问题:
本题的上升序列最高点在中间,可以分别求出正序和反序的LIS,再枚举每一个点的正反向LIS长度之和,即为本题中所求最大长度;
总人数减去这个最大长度即为最少出列人数.
public static void main(String[] args) {
int n=sc.nextInt(),ans=0;
//下标从1-n
int[] T=new int[n+2],dp1=new int[n+2],dp2=new int[n+2];
for(int i=1;i<=n;i++) T[i]=sc.nextInt();
//从1到n求LIS
for(int i=1;i<=n;i++)
for(int j=0;j<i;j++)
if(T[i]>T[j]) dp1[i]=Math.max(dp1[i],dp1[j]+1);
//从n到1求LIS
for(int i=n;i>=1;i--)
for(int j=n+1;j>i;j--)
if(T[i]>T[j]) dp2[i]=Math.max(dp2[i],dp2[j]+1);
for(int i=1;i<=n;i++)
//枚举Ti,从1到Ti的LIS长度+从TK到Ti的LIS长度-1(Ti被算了两次)
ans=Math.max(dp1[i]+dp2[i]-1,ans);
out.println(n-ans);
out.flush();
}
J - 牛可乐和最长公共子序列
状态转移方程如下:
- x[i] == y[i]: DPi,j = DPi-1,j-1 +1;
- x[i] <> y[j]: DPi,j = max(DPi-1,j , DPi,j-1);
- i= 0 | | j= 0: DPi,j = 0;
import java.io.*;
import java.util.*;
public class Main {
//dp:字符串1的前i位和字符串2的前j位的LCS长度
static char[] c1,c2;
static int n,m;
static int[][] dp;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
//下标均从1开始
c1=(" "+sc.next()).toCharArray();
c2=(" "+sc.next()).toCharArray();
n=c1.length-1;m=c2.length-1;
dp=new int[n+1][m+1];
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(c1[i]==c2[j]) {
dp[i][j]=dp[i-1][j-1]+1;
}
else {
dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
out.println(dp[n][m]);
}
out.flush();
}
static PrintWriter out=new PrintWriter(
new BufferedWriter(new OutputStreamWriter(System.out)));
}
K - [NOIP2008]传纸条
static int N=60;
static int[][] a=new int[N][N];
static int[][][] F=new int[N*2][N][N];
public static void main(String[] args) {
int m=sc.nextInt(),n=sc.nextInt();
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
a[i][j]=sc.nextInt();
//赋初值 -1
for (int[][] ints:F)
for (int[] Int:ints) Arrays.fill(Int,-1);
F[2][1][1]=0;//最初的点,在左上角,好感度为0
for(int k=3;k<m+n;k++)
for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++){
int s=getMax(F[k-1][i][j],F[k-1][i-1][j],F[k-1][i][j-1],F[k-1][i-1][j-1],F[k][i][j]);
if(s==-1)continue;//当s为-1时,说明四种情况都不能到该点,故不存在。
if(k-i<N&&k-j<N)F[k][i][j]=s+a[k-i][i]+a[k-j][j];//该点的值为最大的前一个值与当前F[k][i][j]表示两点的值的和。
}
//因为i永远小于j,所以右下角的点不会求到,
//但是到右下角只有一种情况,就是在右下角的上面和右下角的左边,直接输出就好了。
out.println(F[m+n-1][n-1][n]);
out.flush();
}
static int getMax(int a,int b,int c,int d,int s){
return Math.max(Math.max(Math.max(a,b),Math.max(c,d)),s);
}
L - 费解的开关(位运算/模拟)
static int N=6;
static int[] dx={-1,0,1,0,0},dy={0,1,0,-1,0};
static char[][] g=new char[N][N];
static String[] backup=new String[N];
public static void main(String[] args) {
int n=sc.nextInt();
while(n-->0){
// 按行输入,把每一行当成一个字符串
for(int i=0;i<5;i++){
String s=sc.next();
g[i]=s.toCharArray();
//把原始数组备份一下,然后操作g,操作完了还原,然后再操作
//注意必须是深拷贝
backup[i]=s;
}
int res=10;
/*
这里我们枚举了第一行的32种按法,不用管是亮是灭,把第一行所有情况都按一遍
按每种情况的第一行,去遍历接下来的行
枚举32种第一行的按法只是可能会减少步数,如果直接从第二行开始答案一定是固定的了,找不到最优解或者可能没有解
*/
for (int op=0;op<32;op++){
int step=0;
// 第一行的按法(在这里 1表示按了, 0表示不按),这里只是为了输出第一行按完之后的状态
for (int i=0;i<5;i++)
if ((op>>i&1)==1){
/*
数字2对应了 00010 表示第2个位置的按一下
00010 >> 1 & 1 是1所以turn(0, 1)就是第一行第二个位置
数字3对应了 00011 表示第1和第2个位置的按一下
*/
step++;
turn(0,i);
}
// 然后通过第一行按完之后的状态,按234行
for (int i=0;i<4;i++)
for (int j=0;j<5;j++)
if (g[i][j]=='0'){
step++;
turn(i+1,j); //如果这个位置是灭的,就按下一行对应的位置
}
//判断最后一行是否全亮
boolean dark=false;
for (int j=0;j<5;j++)
if(g[4][j]=='0'){
dark=true;
break;
}
// 对于32种情况的这一种,如果所有的全亮就记录下步数(事实上只记录了最后一行是否dark)
if(!dark) res=Math.min(res,step);
for(int i=0;i<5;i++) {
g[i]=backup[i].toCharArray();
}
}
if(res>6) res=-1;
out.println(res);
}
out.flush();
}
// 这个操作是把(x, y)以及上下左右的灯都变成相反的颜色
static void turn (int x,int y){
for(int i=0;i<5;i++) {
int a=x+dx[i];
int b=y+dy[i];
//超出临界范围,跳过
if (a<0||a>=5||b<0||b>=5) continue;
if(g[a][b]=='0')g[a][b]='1';
else g[a][b]='0';
}
}