暑假去斯坦福学一门叫Learning and Memory: Theory and Practice的课，不知道能不能提升一下我的脑力呢？（笑
分块
P1463 智商问题
1 |
|
动态规划、递推
BZOJ2442: [Usaco2011 Open]修剪草坪
动态规划+单调队列优化（水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
36
37
38
39
40
41
42
43
typedef long long ll;
using namespace std;
ll read(){
ll x = 0, f = 1; char ch = getchar();
while (ch > '9' || ch < '0'){ if (ch == '-') f = -1; ch = getchar();}
while (ch <= '9' && ch >= '0'){ x = x * 10 + ch -'0'; ch = getchar();}
return x*f;
}
ll sum[100100];
struct node
{
ll pos, value;
}q[100100];
ll f[100100];
int main(){
freopen(filenamein, "r", stdin);
freopen(filenameout, "w", stdout);
// f[i] = max(f[j] + sum[i] - sum[j + 1] ) (i - k <= j)
// f[i] = sum[i] + max(f[j] - sum[j + 1]) ( j >= i - k)
int n = read(), k = read();
for (int i = 1; i <= n; i++){
sum[i] = read() + sum[i-1];
}
int h = 1, t = 1;
q[1].pos = 0;
q[1].value = 0;
for (int i = 1; i <= n; i++){
while (h <= t && q[h].pos < i - k) h++;
f[i] = sum[i] + q[h].value;
while (h <= t && q[t].value < f[i - 1] - sum[i]) t--;
q[++t].pos = i;
q[t].value = f[i - 1] - sum[i];
}
printf("%lld\n", f[n]);
return 0;
}
BZOJ3675: [Apio2014]序列分割
Description
小H最近迷上了一个分隔序列的游戏。在这个游戏里，小H需要将一个长度为n的非负整数序列分割成k+1个非空的子序列。为了得到k+1个子序列，小H需要重复k次以下的步骤：
1.小H首先选择一个长度超过1的序列（一开始小H只有一个长度为n的序列——也就是一开始得到的整个序列）；
2.选择一个位置，并通过这个位置将这个序列分割成连续的两个非空的新序列。
每次进行上述步骤之后，小H将会得到一定的分数。这个分数为两个新序列中元素和的乘积。小H希望选择一种最佳的分割方式，使得k轮之后，小H的总得分最大。
Input
输入第一行包含两个整数n，k（k+1≤n）。
第二行包含n个非负整数a1，a2，…，an（0≤ai≤10^4），表示一开始小H得到的序列。
Output
输出第一行包含一个整数，为小H可以得到的最大分数。
Sol
动态规划 + 斜率优化
首先得发现得了这道题切割的顺序其实是不影响答案的。
然后有方程式：
$$f(i,t+1)=max(f(j,t)+s(i)*s(j)-s(j)^{2})$$
要是没有s(i)*s(j)单调队列就行了。
有的话可以单调队列+斜率优化。
具体可以看一下这个博客
1 |
|
图论
BZOJ1823: [JSOI2010]满汉全席
2-SAT 大概就是用来解决一堆逻辑关系的时候用的。
每个点拆成真和假然后根据逻辑关系连边。然后一顿DPS。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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
typedef long long ll;
using namespace std;
int read(){
int x = 0, f = 1; char ch = getchar();
while (ch > '9' || ch < '0'){ if (ch == '-') f = -1; ch = getchar();}
while (ch <= '9' && ch >= '0'){ x = x * 10 + ch -'0'; ch = getchar();}
return x*f;
}
int get(){
char ch = getchar();
while (ch != 'm' && ch != 'h') ch = getchar();
if (ch == 'm') return 1;
return 0;
}
int n, m;
int fir[1000], e = 0;
struct edge{
int u, v, nex;
}ed[4000];
void addedge(int x, int y){
ed[++e].u = x;
ed[e].v = y;
ed[e].nex = fir[x];
fir[x] = e;
}
stack <int> s;
bool vis[4000];
bool dfs(int u){
if (vis[u ^ 1]) return false;
if (vis[u]) return true;
vis[u] = true;
s.push(u);
for (int i = fir[u]; i; i = ed[i].nex){
int v = ed[i].v;
if (!dfs(v)) return false;
}
return true;
}
bool solve(){
memset(vis, 0, sizeof vis);
for (int i = 1; i <= n; i++)
if (!vis[2 * i] && !vis[2 * i + 1]){
while (!s.empty()) s.pop();
if (!dfs(2 * i)) {
while (!s.empty()) {vis[s.top()] = 0; s.pop();}
if (!dfs(2 * i + 1)) return false;
}
}
return true;
}
int main(){
freopen(filenamein, "r", stdin);
freopen(filenameout, "w", stdout);
int t = read();
while(t--){
n = read(); m = read();
memset(ed, 0, sizeof ed);
e = 0;
memset(fir, 0, sizeof fir);
for (int i = 1; i <= m; i++){
int type1 = get(), x = read();
int type2 = get(), y = read();
addedge(2 * x + (1 - type1), 2 * y + type2);
addedge(2 * y + (1 - type2), 2 * x + type1);
}
if (solve()) printf("GOOD\n");
else printf("BAD\n");
}
return 0;
}
可并堆左偏树
BZOJ1455: 罗马游戏
1 |
|