一.最长上升（下降）子序列
https://www.luogu.org/problemnew/show/P1091
https://www.luogu.org/problemnew/show/P1020
P1091：
让每一个人做最中间人，然后分别求到俩边的最长下降子序列
注意要选取中间人为最高的对比
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
|
int a[MAX];
int dp[MAX];
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >>N;
for(int i = 1;i <= N;i++)
{
cin >> a[i];
}
int mi = INF;
for(int k = 1;k <= N;k++)
{
fill(dp,dp+MAX,0);
int ans =0;
dp[0] = a[k];
for(int i = k-1;i >= 1;i--)
{
for(int j = k-1;j >= 1;j--)
{
if(dp[j-1] > a[i])
{
dp[j] = max(a[i],dp[j]);
}
if(dp[j] != 0 && j > ans) ans = j;
}
}
int x = k - 1 - ans;
fill(dp,dp+MAX,0);
dp[0] = a[k];
ans = 0;
for(int i = k+1;i <= N;i++)
{
for(int j = N-k;j >= 1;j--)
{
if(dp[j-1] > a[i])
{
dp[j] = max(a[i],dp[j]);
}
if(dp[j] != 0 && j > ans) ans = j;
}
}
int y = N - k - ans;
if(mi > x + y)
{
mi = x + y;
}
}
cout << mi;
return 0;
}
|
P1020
状态转移方程和上面一样
dp[i]代表的是截拦i个火箭的时候的最高高度，不能截拦的时候为0
关键语句：
1
2
3
4
| if(dp[j-1] >= a[i])
{
dp[j] = max(a[i],dp[j]);
}
|
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
|
int a[MAX];
int dp[MAX];
vector<int> b;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
N= 1;
int x;
int cnt = 0;
while(cin >> x)
{
a[N++] = x;
if(b.size() == 0)
{
b.push_back(x);
cnt++;
}
else
{
int i= 0;
for(i = 0;i < cnt;i++)
{
if(b[i] >= x)
{
b[i] = x;
break;
}
}
if(i == cnt)
{
b.push_back(x);
cnt++;
}
}
sort(b.begin(),b.end());
}
N--;
dp[0] = INF;
for(int i = 1;i <= N;i++)
{
if(dp[i-1] >= a[i])
{
dp[i] = a[i];
}
for(int j = i-1;j >= 1 ;j--)
{
if(dp[j-1] >= a[i])
{
dp[j] = max(a[i],dp[j]);
}
}
}
for(int i = N;i >= 1;i--)
{
if(dp[i] != 0)
{
cout << i <<"\n";
break;
}
}
cout << cnt ;
return 0;
}
|
二.区间dp
https://www.luogu.org/problemnew/show/P1880
p1880：
首先这个题是环，我们要把环化为链
1
2
3
4
5
| for(int i = 1;i <= N;i++)
{
cin >> a[i];
a[i+N] = a[i];
}
|
还有做一下前缀和的处理，前缀和就是前面的数组元素的和
1
2
3
4
| for(int i = 1;i <= 2*N;i++)
{
sum[i] = sum[i-1] + a[i];
}
|
dp[i][j] 代表的是区间（i，j）的最大和or小
首先我们枚举的是区间的长度，而不是（i，j）
一旦区间长度l确定了，枚举i，j是固定的
然后通过k，把俩堆堆到一起
关键代码：dpa[i][k] + dpa[k+1][j] 注意后面是k+1不是k
1
2
| dpa[i][j] = max(dpa[i][j],dpa[i][k] + dpa[k+1][j] + sum[j] - sum[i-1]);
dpi[i][j] = min(dpi[i][j],dpi[i][k] + dpi[k+1][j] + sum[j] - sum[i-1]);
|
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
|
int a[2*MAX];
int dpa[2*MAX][2*MAX];
int dpi[2*MAX][2*MAX];
int sum[2*MAX];
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N;
for(int i = 1;i <= N;i++)
{
cin >> a[i];
a[i+N] = a[i];
}
sum[0] = 0;
for(int i = 0;i <= N;i++)
{
fill(dpa[i],dpa[i]+N+1,0);
fill(dpi[i],dpi[i]+N+1,0);
}
for(int i = 1;i <= 2*N;i++)
{
sum[i] = sum[i-1] + a[i];
}
for(int l = 2;l <= N;l++)
{
for(int i = 1;i+l-1 <= 2*N;i++)
{
int j = i + l - 1;
dpi[i][j] = INF;
for(int k = i;k < j;k++)
{
dpa[i][j] = max(dpa[i][j],dpa[i][k] + dpa[k+1][j] + sum[j] - sum[i-1]);
dpi[i][j] = min(dpi[i][j],dpi[i][k] + dpi[k+1][j] + sum[j] - sum[i-1]);
}
}
}
int ma = 0;
int mi = INF;
for(int i = 1;i <= N;i++)
{
ma = max(ma,dpa[i][i+N-1]);
mi = min(mi,dpi[i][i+N-1]);
}
cout << mi << "\n" << ma << "\n";
return 0;
}
|