塞 尔 达 是 天

Zuma题面翻译$texttt{Genos}$ 最近在他的手机上下载了祖玛游戏。在祖玛游戏里，存在 $n$ 个一行的宝石，第 $i$ 个宝石的颜色是 $C_i$。这个游戏的目标是尽快的消灭一行中所有的宝石。 在一秒钟，$texttt{Genos}$ 能很快的挑选出这些有颜色的宝石中的一个回文的、连续的子串，并将这个子串移除。每当一个子串被删除后，剩余的宝石将连接在一起，形成一个新的行列。 你的任务是：求出把整个宝石串都移除的最短时间。 输入格式第一行包含一个整数 $n(1 \leq n \leq 500)$，表示宝石串的长度。第二行包含 $n$ 个被空格分开的整数，第 $i(1 le i le n)$ 个表示这行中第 $i$ 个珠子的颜色。 输出格式输出一个整数，把这行珠子移除的最短时间。 样例说明在第一个例子中，$texttt{Genos}$ 可以在一秒钟就把这行珠子全部移走。在第二个例子中，$texttt{Genos}$ 一次只能移走一个珠子，所以移走三个珠子花费他三秒。在第三个例子中，为了达到 $2$ 秒的最快时间，先移除回文串 $texttt{4 4}$,再移除回文串 $tex ...

[IOI2000] 回文字串题目背景IOI2000 第一题 题目描述回文词是一种对称的字符串。任意给定一个字符串，通过插入若干字符，都可以变成回文词。此题的任务是，求出将给定字符串变成回文词所需要插入的最少字符数。 比如 $\verb!Ab3bd!$ 插入 $2$ 个字符后可以变成回文词 $\verb!dAb3bAd!$ 或 $\verb!Adb3bdA!$，但是插入少于 $2$ 个的字符无法变成回文词。 注意：此问题区分大小写。 输入格式输入共一行，一个字符串。 输出格式有且只有一个整数，即最少插入字符数。 样例 #1样例输入 #11Ab3bd 样例输出 #112 提示数据范围及约定记字符串长度为 $l$。 对于全部数据，$0<l\le 1000$。 思路 代码123456789101112131415161718192021222324class Main { public static int N = 1010; public static int[][] dp = new int[N][N]; public static BufferedR ...

[NOIP2010 提高组] 乌龟棋题目背景NOIP2010 提高组 T2 题目描述小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。 乌龟棋的棋盘是一行 $N$ 个格子，每个格子上一个分数（非负整数）。棋盘第 $1$ 格是唯一的起点，第 $N$ 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。 乌龟棋中 $M$ 张爬行卡片，分成 $4$ 种不同的类型（$M$ 张卡片中不一定包含所有 $4$ 种类型的卡片，见样例），每种类型的卡片上分别标有 $1,2,3,4$ 四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。 游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。 很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡片使用顺序使得最终游戏得分最多。 现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你 ...

[USACO03FALL] Cow Exhibition G题目背景题目描述奶牛想证明它们是聪明而风趣的。为此，贝西筹备了一个奶牛博览会，她已经对 $N$ 头奶牛进行了面试，确定了每头奶牛的智商和情商。 贝西有权选择让哪些奶牛参加展览。由于负的智商或情商会造成负面效果，所以贝西不希望出展奶牛的智商之和小于零，或情商之和小于零。满足这两个条件下，她希望出展奶牛的智商与情商之和越大越好，请帮助贝西求出这个最大值。 输入格式第一行：单个整数 $N$，$1 \le N \le 400$。 第二行到第 $N+1$ 行：第 $i+1$ 行有两个整数：$S_i$ 和 $F_i$，表示第 $i$ 头奶牛的智商和情商，− $1000 \le S_i;F_i \le 1000$。 输出格式输出单个整数：表示情商与智商和的最大值。贝西可以不让任何奶牛参加展览，如果这样做是最好的，输出 $0$。 样例 #1样例输入 #11234565-5 78 -66 -32 1-8 -5 样例输出 #118 提示选择第一头，第三头，第四头奶牛，智商和为−5+6+2 = 3，情商和为7−3+1 = 5 ...

import java.util.;import java.io.; class Main { public static int N = 1010, M = 210, P = 1000000007; public static int[][][][] dp = new int[2][M][M][2]; // 使用滚动数组优化 public static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int n = sc.nextInt(), m = sc.nextInt(), K = sc.nextInt(); String s = sc.next(), t = sc.next(); for (int i = 0; i <= n; i++) dp[i % 2][0][0][0] = 1; // 初始化优化 for (int i = 1; i ...

快速求和【动态规划2】线性状态动态规划：P1874 快速求和 题目描述给定一个数字字符串，用最小次数的加法让字符串等于一个给定的目标数字。每次加法就是在字符串的某个位置插入一个加号。在里面要的所有加号都插入后，就像做普通加法那样来求值。 例如，考虑字符串12，做 $0$ 次加法，我们得到数字 $12$。如果插入 $1$ 个加号，我们得到 $3$，因此，这个例子中，最少用 $1$ 次加法就得到数字 $3$。 再举一例，考虑字符串303和目标数字 $6$，最佳方法不是3+0+3。而是3+03。能这样做是因为一个数的前导 $0$ 不会改变它的大小。 输入格式第一行：一个字符串 $s$。 第二行：一个整数 $n$。 输出格式一行一个整数表示最少的加法次数让 $s$ 等于 $n$。如果怎么做都不能让 $s$ 等于 $n$ ，则输出 $-1$。 样例 #1样例输入 #1129999945 样例输出 #114 提示数据规模与约定对于 $100%$ 的数据，保证 $1\le \operatorname{len}(s)\le40$，$1 \leq n\le10^5$。 解题思路 需要注意，我们这个字 ...

大师【动态规划2】线性状态动态规划：P4933 大师 题目背景建筑大师最近在跟着数学大师 ljt12138 学数学，今天他学了等差数列，ljt12138 决定给他留一道练习题。 题目描述ljt12138 首先建了 $n$ 个特斯拉电磁塔，这些电塔排成一排，从左到右依次标号为 $1$ 到 $n$，第 $i$ 个电塔的高度为 $h[i]$。 建筑大师需要从中选出一些电塔，然后这些电塔就会缩到地下去。这时候，如果留在地上的电塔的高度，从左向右构成了一个等差数列，那么这个选择方案就会被认为是美观的。 建筑大师需要求出，一共有多少种美观的选择方案，答案模 $998244353$。 注意，如果地上只留了一个或者两个电塔，那么这种方案也是美观的。地上没有电塔的方案被认为是不美观的。 同时也要注意，等差数列的公差也可以为负数。 输入格式第一行一个正整数 $n$。 第二行 $n$ 个非负整数，第 $i$ 个整数是第 $i$ 个电塔的高度 $h[i]$。 输出格式输出一个整数，表示美观的方案数模 $998244353$ 的值。 样例 #1样例输入 #112813 14 6 20 27 34 34 41 ...

题目描述 解题思路这个题目其实可以从二维问题转换成一个线性dp问题，只需要从1-m个给出的每个鼹鼠出现的信息，找出一个最长的子序列，这个子序列满足，相邻操作是可以满足移动要求的。我们相邻两个操作只要满足两个点的曼哈顿距离小于或者等于时间差，就可以移动。dp[i][j]：从1-i个操作序列中选，以j结尾的最长序列长度。题目需要将二维优化成一维。 代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849import java.io.*;import java.util.*;class Main{ public static int N = 10010; public static int[] dp = new int[N]; public static int[][] pa = new int[20][20]; public static Opration[] ops = new Opration[N]; public sta ...

题目描述 解题思路这个题目我们可以转换一些思维，我们主要求每个位置的左边，右边比她小的数字,两边的数字相乘就会得到最后的结果。然而求位置之后比她小的数字正好就是树状数组的功能。我们只需要维护一个y数组，也就是如果我们这个位置是y，那么y数组的y下标值+1。顺序遍历求y之前小于他的个数，那就是求y数组1-y-1的前缀和。 代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950import java.io.*;import java.util.*;class Main{ public static int N = 200010,n; public static int[] a = new int[N],y = new int[N]; public static long[] lower = new long[N],c = new long[N],greater = new long[N]; public static Buff ...