7-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

#include <iostream>
#include <cstring>
using namespace std;
const int N = 510 , MAX = 1e9 ;
int n;
int a[N][N] ,f[N][N] ; 
int main () {
    cin >> n ;
    for (int i = 1 ; i <= n ; i ++ ) 
        for (int j = 1 ; j <= i ; j ++ ) 
			cin >> a[i][j] ;
    
    for (int i = 0 ; i <= n ; i++) 
        for (int j = 0 ; j <= i + 1 ; j ++ ) 
            f[i][j] = -MAX ;

    f[1][1] = a[1][1];
    for (int i = 2 ; i <= n ; i ++ ) {
        for (int j = 1;j <= i;j++) {
            f[i][j] = max (f[i - 1][j - 1],f[i - 1][j]) + a[i][j];
        }
    }
    int ans = -MAX ;
    for (int i = 1 ; i <= n ; i ++ ) ans = max (ans , f[n][i] ) ;
    cout << ans << endl ; 
}

7-2

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

#include <iostream>
#include <cstring>
using namespace std;
const int N = 510 , MAX = 1e9 ;
int n;
int a[N][N] ,f[N][N] ; 
int main () {
	cin >> n ;
    if(n <= 2){
    	cout << n << endl ;
    	return 0 ;
	}
    int a = 0, b = 0, c = 1;
    for (int i = 1 ; i <= n ; ++ i ) {
        a = b ; 
        b = c ; 
        c = a + b ;
    }
	cout << c << endl ;
}

7-3

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<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int N = 1e3 + 10 ;
int main( ) {

	int n ; 
	cin >> n ;
	vector<int> arr(n) ;
	for( int i = 0 ; i < n ; i ++ ) cin >> arr[i] ;
		
	vector<int> stk ;
	stk.push_back(arr[0]) ;
	for( int i = 1 ; i < n ; i ++ ){
		if( arr[i] > stk.back() ){
			stk.push_back(arr[i]) ;
		}else{
			*lower_bound(stk.begin() , stk.end() , arr[i] ) = arr[i] ;
		}
	}
	cout << stk.size() << endl ;
	
}

7-4

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

#include<bits/stdc++.h>
using namespace std ;
const int N = 1010 ;
int n , m , f[N][N] ;
string s1 , s2 ;
int main(){
    cin >> s1 >> s2 ;
    n = s1.size() , m = s2.size() ;
    s1 = "." + s1 , s2 = "." + s2 ;
    for( int i = 1 ; i <= n ; i ++ ){
        for( int j = 1 ; j <= m ; j ++ ){
            if( s1[i] == s2[j] ){
                f[i][j] = f[i - 1][j - 1] + 1 ;
            }else{
                f[i][j] = max( f[i-1][j] , f[i][j-1] ) ;
            }
        }
    }
    cout << f[n][m] ;
}

7-5

本题的第三个测试点有问题,需要按照以后每一发炮弹不能超过且等于前一发的高度才能AC

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<vector>
#include<algorithm>

int main()
{
    int n;
    while(std::cin >> n)
    {
        std::vector<int> a(n);
        for (int i{}; i != n; ++i)
        {
            std::cin >> a[i];
        }
        std::vector<int> ends;
        for (int v: a)
        {
            auto it{ std::upper_bound(ends.begin(), ends.end(), v) };
            if (it == ends.end())
            {
                ends.push_back(v);
            } else
            {
                *it = v;
            }
        }
        std::cout << ends.size() << '\n';
    }

    return 0;
}

7-6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int dp[N] ;
int n , m ;
int v[N] , w[N] ;
int main(){
    cin >> n >> m ;
    for(int i = 1 ; i <= n ; i ++ )
        cin >> v[i] >> w[i] ;
	for(int i = 1 ; i <= n ; i ++ ){
    	for(int j = m ; j >= v[i] ; j--){
        	dp[j] = max(dp[j] , dp[j - v[i]] + w[i] );
    	}
	}
    cout << dp[m] << endl ;
}

7-7

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 <bits/stdc++.h>
using namespace std;
const int N = 2010;
int n, m;
string a , b ;
int f[N][N];
int main(){
    cin >> a >> b ;
    n = a.size() , m = b.size() ;
    a = "." + a , b = "." + b ;

    for (int i = 0; i <= m; i ++ ) f[0][i] = i;
    for (int i = 0; i <= n; i ++ ) f[i][0] = i;

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            if (a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
            else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
        }

    cout << f[n][m] << endl ;  
}

7-8

题目可以看成两个人从左上角走到右下角的和
可以定义状态[i][j][k][m] 表示第一个人走到i,j 第二个人走到k,m的数字和
由于i + j的值是一个定值 为 步数+2
也可以定义状态[k][i][j] 表示第一个人x坐标为i 第二个人x坐标为j,走了k步时的数字和
转移时正常转移，但需要处理两个人走到同一个格子的情况，这种情况只加一次那个格子的值

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

#include<iostream>
#include<array>
#include<algorithm>
#include<iterator>

using int64 = long long;
#define fun auto
constexpr static int N{ 9 + 2 };
constexpr static int N2{ (9 << 1) + 2 };

int n;
std::array<std::array<int,N2>,N> a;
std::array<std::array<std::array<int,N>,N>,N2> dp;

fun solve()
{
    std::cin >> n;
    int x,y,v;
    while(std::cin >> x >> y >> v and x)
    {
        a[x][y] = v;
    }
    // y = k + 2 - x
    dp[0][1][1] = a[1][1];
    for(int k{ 1 },cei{ (n << 1) - 1 }; k < cei; ++k)
    {
        for(int x1{ 1 },c1{ std::min(x1 + k,n) }; x1 <= c1; ++x1)
        {
            for(int x2{ 1 },c2{ std::min(x2 + k,n)}; x2 <= c2; ++x2)
            {
                dp[k][x1][x2] = std::max({
                                                 dp[k - 1][x1][x2],
                                                 dp[k - 1][x1 - 1][x2],
                                                 dp[k - 1][x1][x2 - 1],
                                                 dp[k - 1][x1 - 1][x2 - 1],
                                         });
                if(x1 == x2)
                {
                    dp[k][x1][x2] += a[x1][k + 2 - x1];
                }
                else
                {
                    dp[k][x1][x2] += a[x1][k + 2 - x1] + a[x2][k + 2 - x2];
                }
            }
        }
    }

    std::cout << dp[(n << 1) - 2][n][n];
}

fun main() -> int
{
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    solve();

    return 0;
}

7-9

正常dp
定义$dp_i$为搜刮前i个超市的最大物资
那么$dp_i = max(dp_{i-1},dp_{i-2} + 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#include<stdio.h>

#define int64 long long
#define N 100002

int64 max(int64 x,int64 y)
{
    if(x < y)
    {
        return y;
    }
    return x;
}

int n;
int a[N];
int64 dp[N];

int main()
{
    scanf("%d",&n);
    for(int i = 1; i <= n; ++i)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        a[i] = y ? x : -x;
    }
    dp[1] = max(a[1],0);
    for(int i = 2; i <= n; ++i)
    {
        dp[i] = max(dp[i - 1],a[i] + dp[i - 2]);
    }
    int64 ans{};
    for(int i = 1; i <= n; ++i)
    {
        ans = max(ans,dp[i]);
    }
    printf("%lld",ans);

    return 0;
}

7-10

每个物资的价值为i,可看成价值为i,重量为i的物品
A,B在分配时,尽量给A的物资接近物资总和的一半，但不超过总和一半的最大值,就是最好的分配
以总和的一半为容量,进行01背包

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<stdio.h>

#define N 5002
#define N2 500002

int max(int x,int y)
{
    if(x < y)
    {
        return y;
    }
    return x;
}

int n;
int a[N];
int dp[N2];

int main()
{
    scanf("%d",&n);
    int sum = 0;
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d",a + i);
        sum += a[i];
    }
    int cap = sum >> 1;
    for(int i = 1; i <= n; ++i)
    {
        for(int j = cap;j >= a[i]; --j)
        {
            dp[j] = max(dp[j],a[i] + dp[j - a[i]]);
        }
    }
    printf("%d",sum - (dp[cap] << 1));

    return 0;
}

7-11

每次购买物品除了消耗 $b_i$预算还能提升$a_i - b_i$的预算
如果提升的预算大于消耗 则贪心的直接购买
对剩下的物品01背包

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

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define int64 long long
#define N 5002

struct node
{
    int price;
    int discount;
    int k;
};

int64 max(int64 x,int64 y)
{
    if(x < y)
    {
        return y;
    }
    return x;
}

int n,w;

node arr[N];
int sz = 1;

int main()
{
    scanf("%d %d",&n,&w);
    int64 ans{};
    for(int i = 1; i <= n; ++i)
    {
        int a,b,k;
        scanf("%d %d %d",&a,&b,&k);
        if(a - b >= b)
        {
            ans += k;
            w += a - (b << 1);
        }
        else
        {
            arr[sz++] = { b,a - b,k };
        }
    }
    int64* dp = (int64*)malloc((w + 1) * sizeof(int64));
    memset(dp,0,(w + 1) * sizeof(int64));

    for(int i = 1; i != sz; ++i)
    {
        for(int j = w;j + arr[i].discount >= arr[i].price; --j)
        {
            dp[j] = max(dp[j],arr[i].k + dp[j + arr[i].discount - arr[i].price]);
        }
    }

    printf("%lld",ans + dp[w]);
    free(dp);

    return 0;
}

7-12

按经验值e1升序排序,e1相等时按e2降序排序
以e2为关键字求一维最长上升子序列即可

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



#include<iostream>
#include<vector>
#include<algorithm>
#include<iterator>

#define fun auto
#define range(v) v.begin(),v.end()

struct node
{
    fun friend operator>>(std::istream& is,node& n) noexcept -> std::istream&
    {
        return is >> n.exp1 >> n.exp2;
    }
    int exp1,exp2;
};


fun solve()
{
    int n;
    std::cin >> n;
    std::vector<node> a;
    std::copy_n(std::istream_iterator<node>{ std::cin },n,std::back_inserter(a));
    std::sort(range(a),[](const auto n1,const auto n2) noexcept { return n1.exp1 == n2.exp1 ? n1.exp2 > n2.exp2 : n1.exp1 < n2.exp1; });
    std::vector<int> ends;
    for(auto [exp1,exp2] : a)
    {
        auto it{ std::lower_bound(range(ends),exp2) };
        if(it == ends.end())
        {
            ends.push_back(exp2);
        }
        else
        {
            *it = exp2;
        }
    }
    std::cout << ends.size();
}

fun main() -> int
{
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    solve();

    return 0;
}