小明上学,老师布置了 n 个作业,每个作业恰好需要一天做完,每个作业都有最后提交时间ti及其逾期的扣分ki。已知作业n = 3,每个作业的最后提交时间t = [1,3,1],作业逾期扣分k = [6,2,3]。以输入n = 0时作为结束,请给出小明做作业的顺序,以便扣最少的分数。使用动态规划算法和C++进行实现
时间: 2024-02-17 12:04:07 浏览: 37
以下是使用动态规划算法和C++实现的程序,可以求出小明做作业的顺序,以便扣最少的分数:
```cpp
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 1005;
int dp[MAXN][MAXN], t[MAXN], k[MAXN];
int main()
{
int n;
cin >> n;
while (n)
{
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++)
{
cin >> t[i] >> k[i];
}
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= t[i] - 1; j++)
{
dp[i][j] = dp[i - 1][j];
}
for (int j = t[i]; j <= MAXN - 1; j++)
{
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - t[i]] + k[i]);
}
}
int ans = 0;
for (int j = 0; j <= MAXN - 1; j++)
{
ans = max(ans, dp[n][j]);
}
cout << ans << endl;
cin >> n;
}
return 0;
}
```
程序中,dp[i][j]表示前i个作业在截止日期为j时的最小扣分,t[i]表示第i个作业的截止日期,k[i]表示第i个作业逾期扣分。程序的主要思路是通过动态规划算法,求解出dp数组,并且找到最小的扣分。时间复杂度为O(n*T),其中T为所有作业截止时间的最大值。
输入示例:
```
3
1 6
3 2
1 3
0
```
输出示例:
```
3
```