胡棕宪

题解

/ 注册

全部文章 / 题解（共9篇）

队伍配置（dp）

题意：略。题记：每一个从者和礼装都当成是一个物品，那么物品只有选和不选两种情况。（背包的思想） dp[i][j][k][l]表示前i个物品cost值为j选了k个从者和l件礼装。在循环时可以把数组第一维优化掉（跟背包问题一样优化）。在输入从者时:dp[j][k][0]=max(dp[j][k][...

2020-06-30

0 803

滑动窗口

题意：略。题记：取区间最大值的情况：取维护一个双端队列，每当a[i]进入队尾时，在a[i]之前进入队列且比a[i]小的数是不可能成为区间最大值了，所以这些数可以在队列中删掉。取最小值同理。 #include<bits/stdc++.h> using namespace std; co...

2020-06-28

1 655

数学考试（前缀和）

题意：找出两个长度为k的区间和最大。题记：前缀和处理一下数组，然后枚举区间的右端点，mmax记录下第一个区间和的最大值，再取第二个区间和mmax的最大值即是答案。 #include<bits/stdc++.h> using namespace std; #define int lon...

2020-06-28

0 506

[SCOI2005]最大子矩阵（dp）

题意：略题记：由于m的范围在1 ≤ m ≤ 2。所以很容易就想到dp。dp[i][j][k]表示的是在第一列的前i个数，第二列的前j个数选k个矩阵的最大值。那么dp过程中大致有两种情况：1、不需要重新选一个新矩阵dp[i][j][k]=max(dp[i][j-1][k],dp[i-1][j][k...

2020-06-26

0 516

小A和小B（BFS）

题意：略。题记：将小A和小B做为起点BFS两次，分别记录下小A和小B到每个位置的时间，最后枚举小A和小B相遇的位置，取小A和小B到当前位置的时间的最大值（相当于小A和小B在这个位置相遇）。 #include<bits/stdc++.h> using namespace std; co...

2020-06-25

0 639

小A买彩票（dp）

题意：略题记：dp[i][j]表示前i张彩票能组成总金额为j元的方案数第i张彩票有1,2,3,4元四种选择，所以总金额为j的情况可以由四种情况转移过来。dp[i][j]=dp[i-1][j-1]+dp[i-1][j-2]+dp[i-1][j-3]+dp[i-1][j-4]; 总方案数是4的n次方种...

2020-06-25

0 861

[SCOI2009]粉刷匠（dp）

参考题解题意：略。题记：dp[i][j][k][0/1]表示为前i条j段涂k次，最后一段涂红/蓝的最多正确格子数。可以理解为将所有木条分成了n*m的木块。然后一块一块地填。那么可以分成两种情况：1、当前木块是整条木板的第一块，一定要进行一次新的涂色。（即j为1的情况）由上一条木条的最后一块木板...

2020-06-25

0 676

Forsaken喜欢数论

题意：求出1-n所有数的最小质因子之和。题记：筛质数的模板题。用每一个数的最小质因子取筛掉这个数，同时把这个质数加到答案中。 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=...

2020-06-24

0 638

Three States（BFS）

题目大意：有一个n*m的大陆，在大陆上有三个州（1、2、3），现在需要三个州相连，求最少需要修建多少个单元格作为道路。题记：首先要了解一下01BFS。bfs可以O（V+E）求解边权全为1的图上的最短路，但是当边权只有0或者1时，可以使用01BFS来快速求解。 01BFS维护一个双端队列，当边权为0...

2020-06-20

1 699