某学科老师布置了n个题目,每个题目都有相应的分数及截止日期。各个题目的分数及截止日期可能并不相同。对某题目而言,如果在该题目的截止日期前完成则可获得对应的分数,否则无法得分。假设每个题目均需要花费一天的时间来完成,这期间无法完成其他题目。请你设计算法指定题目的完成计划,从而使总的得分最大。写出C++代码
时间: 2024-02-01 17:15:03 浏览: 120
这是一个经典的动态规划问题,可以使用背包问题的思想来解决。具体步骤如下:
1. 将所有题目按照截止日期从早到晚排序。
2. 设dp[i][j]表示前i个题目,在时间不超过j的情况下可以获得的最大得分。
3. 对于每个dp[i][j],考虑两种情况:
- 不做第i个题目,即dp[i][j] = dp[i-1][j]。
- 做第i个题目,即dp[i][j] = dp[i-1][j-1] + score[i],其中score[i]表示第i个题目的得分。
4. 取dp[n][n]即为最终的最大得分。
C++代码如下:
```c++
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1005;
int n, dp[N][N], score[N], ddl[N];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> score[i] >> ddl[i];
}
// 按截止日期从早到晚排序
for (int i = 1; i <= n; i++) {
for (int j = i+1; j <= n; j++) {
if (ddl[i] > ddl[j]) {
swap(ddl[i], ddl[j]);
swap(score[i], score[j]);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (j >= ddl[i]) {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + score[i]);
} else {
dp[i][j] = dp[i-1][j];
}
}
}
cout << dp[n][n] << endl;
return 0;
}
```
阅读全文