动态规划-划分问题1（模板）、划分问题2（模板）、接龙数列

划分问题1模板问题描述一个正整数 nn 可以表示成若干个正整数之和形如 na1a2...akna1​a2​...ak​。其中 a1a2...ak≥1a1​a2​...ak​≥1。给定一个正整数 nn求解 nn 的不同划分方案数。结果需要对 10971097 取模。例如3213213333输入格式输入一行包含一个正整数 nn。(1≤n≤1000)(1≤n≤1000)输出格式输出一行一个整数由于结果可能很大你需要对 10971097 取模。样例输入5样例输出3import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N1010,mod(int)1e97; // static int w[]new int[N]; static int f[]new int[N]; static int n; static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); //定义f[i][j]为只考虑前i个数字 能拼出j的方案数 // for (int i 0; i n; i) { // f[i][0]1; // } // for (int i 1; i n; i) { // for (int j 1; j n; j) { // if(ji)f[i][j]f[i-1][j]; // else f[i][j](f[i-1][j]f[i-1][j-i])%mod; // } // } // bw.write(f[n][n]); f[0]1; for (int i 1; i n; i) { for (int j n; j 1; j--) { if(ji)f[j](f[j]f[j-i])%mod; } } bw.write(f[n]); br.close(); bw.flush(); bw.close(); } }划分问题2模板问题描述一个正整数 nn 可以表示成若干个正整数之和形如 na1a2...akna1​a2​...ak​。其中 a1≥a2≥...≥ak≥1a1​≥a2​≥...≥ak​≥1。给定一个正整数 nn求解 nn 的不同划分方案数。结果对 10971097 取模。例如311131113213213333输入格式输入一行包含一个正整数 nn。(1≤n≤1000)(1≤n≤1000)输出格式输出一行一个整数由于结果可能很大你需要对 10971097 取模。样例输入5样例输出7import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N1010,mod(int)1e97; // static int w[]new int[N]; static int f[][]new int[N][N]; static int n; static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); //定义f[i][j]为数字i 分成j个数的方案数 //我们可以按每个划分的数字是否包含数字1 来进行分类 //若当前集合不包含数字1 //f[i][j]为f[i-1-j-1][j];//我们可以找到一个已经划分为j个数的方案 将其每个数加1 //若当前集合包含数字1 1作为一个单独的数字 还有j-1个数 //f[i][j]f[i-1][j-1]; f[0][0]1; for (int i 1; i n; i) { for (int j 1; j n; j) { // 含 1 的情况 f[i][j] f[i-1][j-1]; // 不含 1 的情况需要 i j if (i j) { f[i][j] (f[i][j] f[i-j][j]) % mod; } } } int res0; for (int i 1; i n; i) { res(resf[n][i])%mod; } bw.write(res); br.close(); bw.flush(); bw.close(); } }接龙数列问题描述对于一个长度为 KK 的整数数列A1,A2,…,AKA1​,A2​,…,AK​我们称之为接龙数列当且仅当 AiAi​ 的首位数字恰好等于 Ai−1Ai−1​ 的末位数字 (2≤i≤K)(2≤i≤K)。例如 12,23,35,56,61,1112,23,35,56,61,11 是接龙数列12,23,34,5612,23,34,56 不是接龙数列因为 5656 的首位数字不等于 3434 的末位数字。所有长度为 11 的整数数列都是接龙数列。现在给定一个长度为 NN 的数列 A1,A2,…,ANA1​,A2​,…,AN​请你计算最少从中删除多少个数可以使剩下的序列是接龙序列输入格式第一行包含一个整数 NN。第二行包含 NN 个整数 A1,A2,…,ANA1​,A2​,…,AN​。输出格式一个整数代表答案。样例输入5 11 121 22 12 2023样例输出1样例说明删除 2222剩余 11,121,12,202311,121,12,2023 是接龙数列。评测用例规模与约定对于 2020% 的数据1≤N≤201≤N≤20。对于 5050% 的数据1≤N≤100001≤N≤10000。对于 100100% 的数据1≤N≤1051≤N≤1051≤Ai≤1091≤Ai​≤109。所有 AiAi​ 保证不包含前导 00。import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N100010; // static int a[]new int[N]; static String num[]new String[N]; static int f[]new int[10]; static int n; static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); stnew StringTokenizer(br.readLine()); for (int i 1; i n; i) { num[i]st.nextToken(); } //定义f[i]为以数字i结尾的接龙序列的最大长度 for (int i 1; i n; i) { int firstnum[i].charAt(0)-0; int lastnum[i].charAt(num[i].length()-1)-0; f[last]Math.max(f[last],f[first]1); } int maxlenInteger.MIN_VALUE; for (int i 0; i 10; i) { maxlenMath.max(maxlen, f[i]); } bw.write((n-maxlen)); br.close(); bw.flush(); bw.close(); } }