集训 DP 专场 01 (9/10).
A. HDU 2041 超级楼梯 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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std ;
const int N = 50 ;
long long f [ N ];
void init () {
f [ 1 ] = 1 , f [ 2 ] = 1 , f [ 3 ] = 2 ;
for ( int i = 4 ; i < N ; i ++ ) {
f [ i ] = f [ i - 1 ] + f [ i - 2 ];
}
}
int main () {
init ();
int n ; cin >> n ;
while ( n -- ) {
int x ; scanf ( "%d" , & x );
printf ( "%lld \n " , f [ x ]);
}
return 0 ;
}
B. POJ 1163 The Triangle 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <algorithm>
using namespace std ;
const int N = 1010 ;
int n ;
int w [ N ][ N ];
int f [ N ][ N ];
int main () {
cin >> n ;
for ( int i = 1 ; i <= n ; i ++ ) {
for ( int j = 1 ; j <= i ; j ++ )
cin >> w [ i ][ j ];
}
for ( int i = n ; i ; i -- ) {
for ( int j = i ; j ; j -- )
f [ i ][ j ] = max ( f [ i + 1 ][ j ], f [ i + 1 ][ j + 1 ]) + w [ i ][ j ];
}
cout << f [ 1 ][ 1 ] << endl ;
return 0 ;
}
C. POJ2419 Maximum Sum做法:求两段不相交区间和的最大值。正反dp一遍求出 $i$ 和 $i$ 左侧的连续区间的最大和,$i$ 和 $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
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std ;
typedef long long LL ;
const int N = 50010 ;
int n , T ;
LL a [ N ];
LL f [ N ], g [ N ];
void solve () {
scanf ( "%d" , & n );
memset ( f , - 0x3f , sizeof f );
memset ( g , - 0x3f , sizeof g );
for ( int i = 1 ; i <= n ; i ++ ) scanf ( "%lld" , & a [ i ]);
for ( int i = 1 ; i <= n ; i ++ ) f [ i ] = max ( a [ i ], f [ i - 1 ] + a [ i ]);
for ( int i = n ; i >= 1 ; i -- ) g [ i ] = max ( a [ i ], g [ i + 1 ] + a [ i ]);
for ( int i = 1 ; i <= n ; i ++ ) f [ i ] = max ( f [ i ], f [ i - 1 ]);
for ( int i = n ; i >= 1 ; i -- ) g [ i ] = max ( g [ i ], g [ i + 1 ]);
LL res = - 1e18 ;
for ( int i = 1 ; i <= n - 1 ; i ++ ) res = max ( res , f [ i ] + g [ i + 1 ]);
cout << res << endl ;
}
int main () {
cin >> T ;
while ( T -- ) solve ();
return 0 ;
}
D. CodeForces 846A Curriculum Vitae做法:最后的序列一定是 0000111 形式的,求非严格 LIS 即可。
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 <iostream>
#include <algorithm>
using namespace std ;
const int N = 110 ;
int n ;
int a [ N ], f [ N ];
int main () {
cin >> n ;
for ( int i = 1 ; i <= n ; i ++ ) cin >> a [ i ];
for ( int i = 1 ; i <= n ; i ++ ) {
f [ i ] = 1 ;
for ( int j = 1 ; j < i ; j ++ ) {
if ( a [ j ] <= a [ i ])
f [ i ] = max ( f [ i ], f [ j ] + 1 );
}
}
int res = 0 ;
for ( int i = 1 ; i <= n ; i ++ ) res = max ( res , f [ i ]);
cout << res << endl ;
return 0 ;
}
E. CodeForces 650D Zip-line(完全不会) F. CodeForces 10D LCIS去年做过的一个题:https://ketchuppp.xyz/post/Codeforces10D-LCIS/
G. CodeForces 1038D Slime(已补)开始还想怎么区间dp,一看数据范围就不太行。 做法:贪心、思维题。最优的情况一定是,只有相邻两项取了差值的绝对值,其他项都可以取到自身的绝对值。所以只要暴力循环一遍,$i$ 和 $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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std ;
typedef long long LL ;
const int N = 500010 ;
int n ;
LL a [ N ], b [ N ];
int main () {
cin >> n ;
LL sum = 0 ;
for ( int i = 1 ; i <= n ; i ++ ) {
scanf ( "%lld" , & a [ i ]);
b [ i ] = abs ( a [ i ]);
sum += b [ i ];
}
LL res = 0 ;
for ( int i = 1 ; i <= n - 1 ; i ++ ) {
// i, i+1
res = max ( res , sum - ( b [ i ] + b [ i + 1 ]) + abs ( a [ i ] - a [ i + 1 ]));
}
if ( n == 1 ) cout << a [ 1 ] << endl ;
else cout << res << endl ;
return 0 ;
}
H. UVA 11584 Partitioning by Palindromes$f[i]$ 表示将前 $i$ 个分割成回文串的最小个数,暴力枚举一下 $j$,$[j,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
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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std ;
typedef long long LL ;
const int N = 1010 ;
int n , T ;
int f [ N ]; // f[i]表示将前i个分割成回文串的最小个数
char s [ N ];
bool check ( int l , int r ) {
int i = l , j = r ;
bool flag = true ;
while ( i < j ) {
if ( s [ i ] != s [ j ]) {
flag = false ;
break ;
}
i ++ , j -- ;
}
return flag ;
}
void solve () {
scanf ( "%s" , s + 1 );
n = strlen ( s + 1 );
memset ( f , 0x3f , sizeof f );
f [ 0 ] = 0 ;
for ( int i = 1 ; i <= n ; i ++ ) {
f [ i ] = f [ i - 1 ] + 1 ;
for ( int j = 1 ; j < i ; j ++ ) {
if ( check ( j , i )) {
f [ i ] = min ( f [ i ], f [ j - 1 ] + 1 );
}
}
}
// cout << check(3, 5) << endl;
// cout << f[5] << endl;
cout << f [ n ] << endl ;
}
int main () {
cin >> T ;
while ( T -- ) solve ();
return 0 ;
}
I. CodeForces 1133E K Balanced Teams(已补)题意:给定 $n$ 个数,分成 $k$ 组,要求组内最大值和最小值的差值不超过 $5$,问 $k$ 组最多能包含几个数。
做法:$f[i][j]$ 表示前 $i$ 个人中分了 $j$ 组的最大人数。以第 $i$ 个人在不组内来划分。 $i$ 不在组内 $f[i][j]=f[i-1][j]$,$i$ 组内 $f[i][j]=f[t-1][j-1]+i-t+1$,其中 $t$ 是第 $j-1$ 组中的最小值的下标,二分查找 $t$。
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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std ;
const int N = 5010 ;
int n , k ;
int a [ N ];
int f [ N ][ N ];
int main () {
cin >> n >> k ;
for ( int i = 1 ; i <= n ; i ++ ) cin >> a [ i ];
sort ( a + 1 , a + n + 1 );
int res = 0 ;
for ( int i = 1 ; i <= n ; i ++ ) {
for ( int j = 1 ; j <= k && j <= i ; j ++ ) {
f [ i ][ j ] = f [ i - 1 ][ j ]; // 不选
int t = lower_bound ( a + 1 , a + i + 1 , a [ i ] - 5 ) - a ;
f [ i ][ j ] = max ( f [ i ][ j ], f [ t - 1 ][ j - 1 ] + i - t + 1 );
res = max ( res , f [ i ][ j ]);
}
}
cout << res << endl ;
return 0 ;
}
J. CodeForces 176B Word Cut(已补)题意:每次可以分割字符串,然后把前面一部分接到后面取,给定步数,原串,目标串,问原串经过特定步数能通过多少种方式变成目标串。
妙啊(然而根本想不到
做法:$f[i][0]$ 表示走了 $i$ 步现在为目标串的所有方案数,$f[i][1]$ 表示走了 $i$ 步现在为非目标串的所有方案数。则答案为 $f[k][0]$。
先把原串看成一个环,从任意位置切开,记录能变成目标串的切割数 $cnt$。
如果第 $i$ 步已经成为了目标串,可以从 $f[i-1][0]$ 和 $f[i-1][1]$ 转移。若 $i-1$ 步已经是目标串了,那么第 $i$ 仍然是目标串,只能从 $cnt-1$ 个位置切;若 $i-1$ 步为非目标串,那么就有 $cnt$ 种切法转化为目标串。
如果第 $i$ 为非目标串,可以从 $f[i-1][0]$ 和 $f[i-1][1]$ 转移。若 $i-1$ 步是目标串了,现在要变成非目标串,只能从 $n-cnt$ 个位置切;若 $i-1$ 步为非目标串,现在要保持非目标串,那么就有 $n-1-cnt$ 种切法(首先不能选择 $cnt$ 个会变成目标串的切法,又不能切成自己当前的状态不然就相当于没切)。
数据范围较小,否则需要 KMP 来做第一步的匹配;另外可以用滚动数组优化一下空间。
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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std ;
typedef long long LL ;
const int N = 2010 , mod = 1e9 + 7 ;
int n , k ;
char a [ N ], b [ N ];
LL f [ 2 ][ 2 ]; // f[i][0]表示第i步变成了b串的方案数,f[i][1]表示第i步变成了非b串的方案数
bool check ( int start ) {
bool flag = true ;
for ( int i = start , j = 0 ; i <= start + n - 1 ; i ++ , j ++ ) {
if ( a [ i ] != b [ j ]) {
flag = false ;
break ;
}
}
return flag ;
}
int main () {
int cnt = 0 ;
scanf ( "%s%s%d" , a , b , & k );
n = strlen ( a );
for ( int i = 0 ; i < n ; i ++ ) {
a [ n + i ] = a [ i ];
if ( check ( i )) cnt ++ ;
}
f [ 0 ][ ! check ( 0 )] = 1 ; // check为true表示a=b
for ( int i = 1 ; i <= k ; i ++ ) {
f [ i & 1 ][ 0 ] = ( f [ i - 1 & 1 ][ 0 ] * ( cnt - 1 ) + f [ i - 1 & 1 ][ 1 ] * cnt ) % mod ;
f [ i & 1 ][ 1 ] = ( f [ i - 1 & 1 ][ 0 ] * ( n - cnt ) + f [ i - 1 & 1 ][ 1 ] * ( n - 1 - cnt )) % mod ;
}
cout << f [ k & 1 ][ 0 ] << endl ;
return 0 ;
}