luogu-P1006

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <cstdio>
#include <algorithm>

const int MAXN = 55;

int m, n, a[MAXN][MAXN], f[MAXN][MAXN][MAXN][MAXN];//f[i][j][k][l] 为两纸条分别传到(i, j),(k, l)的最大好感度
bool flag[MAXN][MAXN] = {};

int MAX(int i, int j, int k, int l) {
	return std::max(std::max(i, j), std::max(k, l));
}

int main() {
	scanf("%d%d", &m, &n);
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%d", &a[i][j]);
		}
	}
	for(int i = 1; i <= m; i++) {
		for(int j = 1; j <= n; j++) {
			for(int k = 1; k <= m; k++) {
				for(int l = 1; l <= n; l++) {//暴力枚举 
					f[i][j][k][l] = MAX(f[i - 1][j][k - 1][l],  f[i - 1][j][k][l - 1], f[i][j - 1][k - 1][l], f[i][j - 1][k][l - 1]) + a[i][j] + a[k][l];
					 //一张纸条有两种传递的方式，两张一共有四种方式，取好感度最大的一个 
					if(i == k && j == l) {//如果走到一个位置 
						f[i][j][k][l] -= a[i][j];//减去其中一个的好感度
					}
				}
			}
		}
	}
	printf("%d", f[m][n][m][n]);
	return 0;
}

题 0X00

题目传送门

CF1324E Sleeping Schedule

分析

这个题由于每次都需要选择，是在ai-1时睡还是ai时睡，那么很明显，这个题需要用动态规划来写。

题目传送门

luogu

分析

暴力的来看 这道题用动态规划求解，则可以定义状态 $ f[i][j][k][l] $ ，表示使用了 $ i $ 张 $ a $ 卡片, $ j $ 张 $ b $ 卡片, $ k $ 张 $ c $ 卡片, $ l $ 张 $ d $ 卡片后可以获得的最大分数，可以将它理解为一个多维的走楼梯问题，每次有 $ 4 $ 种走法

状态转移方程如下

定义

最长上升子序列（Longest Increasing Subsequence，LIS），在计算机科学上是指一个序列中最长的单调递增的子序列。

引自百度百科

状态与状态转移方程

最长上升子序列是序列，其状态是一维的，所以我们可以定义状态 f(i),表示以a[i]结尾的最长上升子序列

如果每一个元素都只考虑它本身，则以a[i]结尾的最长上升子序列长度为一，即它本身，则初始化

替换其实是为后面的元素让出更多的空间，如果有更小的元素，才能插入，如果没有，则对最终结果也没有影响

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 100005;

int x, f[MAXN], n, ans = 1;//f为答案序列

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++) {
		scanf("%d", &x);
		f[i] = x;
		if(x > f[ans]) {
			f[++ans] = x;//如果小于最后一个元素，插入
		}
		else {
			int ind = lower_bound(f + 1, f + 1 + ans, x) - f;//否则，找到第一个大于等于其的元素，进行替换
			f[ind] = x;
		}
	}
	printf("%d", ans);
	return 0;
}

准备

需要两个东西，Java环境和开服包

Java8官网链接
官方开服包链接

检查

在命令行输入以下代码：

快乐五一，充实五一，劳动五一

前言

上物，谓之树焉

基本概念

神奇的队伍

题目描述

你知道吗，在重庆市第八中学校中，流传着四大不可思议的传说。接下来，你将看到四大不可思议之一——神奇的队伍。

相传在八中科技楼的五楼和六楼之间的楼梯的第七步台阶的旁边墙壁上，存在一个隐藏的空间，这个空间中存在着一支神奇的队伍，一支由名为ぎさう的怪异组成的队伍。他们性格散漫，整天以捣蛋搞恶作剧为生，这不，他们又准备出发啦！当然，在他们出发捣乱之前，肯定要先一个一个的排好队，所有的ぎさう一共需要排成n列，当带头的ぎさう喊出稍息的之后，由于这些ぎさう散漫惯了，有迈左腿的，也有迈右腿的，很不整齐。已知在第i列中，有li个ぎさう先迈出了左腿，有ri个ぎさう迈出了右腿。假设所有的ぎさう中，有L个ぎさう迈出左腿，R个ぎさう迈出右腿时，整个队伍的整齐度为|L-R|，现在，带头的ぎさう希望能改变一整列的ぎさう的动作，使得这一列的所有ぎさう之前迈出左腿的现在迈右腿，之前迈右腿的现在迈左腿（当然也可以不改变）。现在带头的ぎさう需要计算，他需要改变哪一列，才能使整个队伍的整齐度最大。如果不改变任何一列，则输出0.

输入格式

第一行一个数字n（1≤n≤100000），表示ぎさう所拥有的列数。

接下来n行，每行两个数字l_i和r_i（1≤l_i，r_i≤500），表示这一列的ぎさう迈出左腿的数量和迈出右腿的数量。

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1

$ hexo new "My New Post"

More info: Writing