Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

FOI2025算法夏令营C班day4——基础动态规划2：区间DP与背包 参考答案

FOI2025

发布于：Jul 16, 2025

代码仅供参考·2025年7月16日8时30分(Day4)·基础动态规划2：区间DP与背包·C++
最后更新于：2025-07-16 20:55:19 | 部分内容由Qwen生成
优先完成标注有【基础】的题目。
Copyright © since 2025 FeatherBlaze (CX2521) All rights reserved.

#A. CDay4P9  前缀和【基础】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
using namespace std;

int n, q, a[100001], s[100001];

int main() {
	cin >> n >> q;
	for (int i=1; i<=n; i++) {
		cin >> a[i];
		s[i] = s[i-1]+a[i];
	}
	while (q--) {
		int x, y;
		cin >> x >> y;
		cout << s[y]-s[x-1] << endl;
	}
  	return 0;
}

#B. CDay4P8  石子合并（弱化版）【基础】

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 <vector>
#include <climits>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> m(n);
    for (int i=0; i<n; i++) {
        cin >> m[i];
    }
    vector<int> pre_sum(n+1, 0);
    for (int i=1; i<=n; i++) {
        pre_sum[i] = pre_sum[i-1]+m[i - 1];
    }
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int len=2; len<=n; len++) {
        for (int i=0; i<=n-len; i++) {
            int j = i+len-1;
            dp[i][j] = INT_MAX;
            for (int k=i; k<j; k++) {
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+(pre_sum[j+1]-pre_sum[i]));
            }
        }
    }
    cout << dp[0][n-1];
    return 0;
}

#C. CDay4P7  [NOI1995] 石子合并

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
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
	int n;
   	cin >> n;
   	vector<int> stones(n*2);
  	for (int i=0; i<n; i++) {
  	    cin >> stones[i];
       	stones[i+n] = stones[i]; 
   	}
   	vector<int> sum(n*2+1, 0);
   	for (int i=1; i<=n*2; i++)  {
      	sum[i] = sum[i-1]+stones[i-1];
   	}
   	vector<vector<int>> dp_min(n*2, vector<int>(n*2, INT_MAX));
  	vector<vector<int>> dp_max(n*2, vector<int>(n*2, INT_MIN));
   	for (int i=0; i<n*2; i++) {
       	dp_min[i][i] = 0;
       	dp_max[i][i] = 0;
   	}
  	for (int len=2; len<=n; len++)
      	for (int i=0; i<=n*2-len; i++) {
           	int j = i+len-1;
           	for (int k=i; k<j; k++) {
               	dp_min[i][j] = min(dp_min[i][j], dp_min[i][k] + dp_min[k + 1][j] + sum[j + 1] - sum[i]);
               	dp_max[i][j] = max(dp_max[i][j], dp_max[i][k] + dp_max[k + 1][j] + sum[j + 1] - sum[i]);
           	}
      	}
  	int min_score = INT_MAX;
   	int max_score = INT_MIN;
   	for (int i=0; i<n; i++)  {
       min_score = min(min_score, dp_min[i][i+n-1]);
       max_score = max(max_score, dp_max[i][i+n-1]);
   	}
   	cout << min_score << endl << max_score;
  	return 0;
}

#D. CDay4P5  双端取数游戏

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>
#include <vector> 
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> nums(N);
    for(int i=0; i<N; i++) {
        cin >> nums[i];
    }
    vector<vector<long long>> dp(N,vector<long long>(N, 0));
    for(int i=0; i<N; i++) {
        dp[i][i] = nums[i];
    }
    for(int len=2; len<=N; len++) {
        for(int i=0; i<=N-len; i++) {
            int j = i+len-1;
            dp[i][j] = max(nums[i]-dp[i+1][j], nums[j]-dp[i][j-1]);
        }
    }
    cout << dp[0][N-1];
    return 0;
}

#E. CDay4P10  [NOIP 2005 普及组] 采药【基础】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int t, m;
	cin >> t >> m;
    vector<int> dp(t+1, 0);
    for(int i=0; i<m; i++) {
        int time, value;
		cin >> time >> value;
        for(int j=t; j>=time; j--) {
            dp[j] = max(dp[j], dp[j-time]+value);
        }
    }
    cout << dp[t] << endl;
    return 0;
}

#F. CDay4P1  平均数取数问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, a; 
    cin >> n >> a; 
    vector<int> x(n); 
    for(int i=0; i<n; i++) cin >> x[i]; 
    vector<vector<long long>> dp(n+1, vector<long long>(n*50+1, 0)); 
    dp[0][0] = 1; 
    for(int i = 0; i < n; i++)
        for(int j = n - 1; j >= 0; j--)
            for(int s = n * 50; s >= 0; s--)
                if(dp[j][s]) dp[j + 1][s + x[i]] += dp[j][s]; 
    long long ans = 0; 
    for(int i=1; i<=n; i++) {
        int sum = i*a; 
        if(sum <= n*50) ans += dp[i][sum]; 
    }
    cout << ans; 
    return 0;
}

#G. CDay4P2  混合药剂

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 <climits>
using namespace std;

int main() {
    int n, ma, mb;
    cin >> n >> ma >> mb;
    vector<vector<long long>> cost(401, vector<long long>(401, LLONG_MAX));
    cost[0][0] = 0;
    for(int i=0; i<n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        vector<vector<long long>> tmp = cost;
        for(int j=0; j<=400; j++) 
            for(int k=0; k<=400; k++) 
                if(cost[j][k] != LLONG_MAX) {
                    int na=j+a, nb=k+b;
                    if(na<=400 && nb<=400) 
                        tmp[na][nb] = min(tmp[na][nb], cost[j][k]+c);
                }
        cost = tmp;
    }
    long long ans = LLONG_MAX;
    for(int i=1; i<=400; i++) 
        for(int j=1; j<=400; j++) 
            if((long long)i*mb == (long long)j*ma) 
                ans = min(ans, cost[i][j]);
    if(ans == LLONG_MAX) cout << -1;
    else cout << ans;
    return 0;
}

#H. CDay4P3  超大背包

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 100001;

int main() {
    int n, w;
    cin >> n >> w;
    vector<long long> dp(MAXN+1, 1e18);
    dp[0] = 0;
    for(int i=0; i<n; i++) {
        int wi, vi;
        cin >> wi >> vi;
        for(int j = MAXN; j >= vi; j--) {
            dp[j] = min(dp[j], dp[j-vi]+wi);
        }
    }
    int ans = 0;
    for(int i=MAXN; i>=0; i--) {
        if(dp[i] <= w) {
            ans = i;
            break;
        }
    }
    cout << ans;
    return 0;
}

#I. CDay4P4  分糖方案

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
#include <iostream>
#include <cstring>
using namespace std;

const int MOD = 1000000007;

int main() {
    int n, k;
    cin >> n >> k;
    int a[105];
    for(int i=0; i<n; i++) cin >> a[i];
    int dp[100005];
    int tmp[100005];
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for(int i=0; i<n; i++) {
        memcpy(tmp, dp, sizeof(dp));
        for(int j=0; j<=k; ++j) dp[j] = 0;
        long long sum = 0;
        for(int j=0; j<=k; j++) {
            int l=min(j, a[i]), start=max(0, j - l);
            sum = (sum+tmp[j])%MOD;
            if(j > a[i]) sum = (sum-tmp[j-a[i]-1]+MOD)%MOD;
            if(j >= 0) dp[j] = sum;
        }
    }
    cout << dp[k];
    return 0;
}

#J. CDay4P6  建塔

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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

struct brick {
    int w, s, v;
};

bool x (brick a, brick b) {
        return a.s+a.w < b.s+b.w;
}

int main() {
    int n;
    cin >> n;
    brick b[1005];
    for(int i=0; i<n; i++) {
        cin >> b[i].w >> b[i].s >> b[i].v;
    }
    sort(b, b+n, x);
    long long dp[50005];
    for(int i=0; i<50005; i++) {
        dp[i] = -1;
    }
    dp[0] = 0;
    for(int i=0; i<n; i++)
	    for(int j=50004; j>=0; j--)
	        if(dp[j]!=-1 && (long long)j<=b[i].s)
	            if(dp[j+b[i].w] < dp[j]+b[i].v)
	                dp[j+b[i].w] = dp[j]+b[i].v;
    long long ans = 0;
    for(int i=0; i<50005; i++)
        if(dp[i] > ans)
            ans = dp[i];
    cout << ans;
    return 0;
}

更新于：Jul 17, 2025

答案

C++

编程

评论