题义是给定一个作业序列，求如何分配使得得到的分数最多。设 dp[i][j] 代表截止到第i个作业，第j天所能够完成的最多分数。
dp方程为：
if (1<= j <= e[i].time) dp[i][j] = max(dp[i-1][j], d[i-1][j-1]+e[i].score);
if (e[i].time+1 <= j <= Last) dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
代码如下：
#include#include #include #include #define MAXN 1005using namespace std;int N, sum, Last, dp[MAXN][MAXN];struct Node{ int time; int score; }e[MAXN];bool cmp(Node a, Node b){ if (a.time != b.time) { return a.time < b.time; } else { return b.score < a.score; }}int DP(){ sort(e+1, e+1+N, cmp); for (int i = 1; i <= N; ++i) { for (int j = 1; j <= e[i].time; ++j) { dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]+e[i].score); } for (int j = e[i].time+1; j <= Last; ++j) { dp[i][j] = max(dp[i-1][j], dp[i][j-1]); } } return dp[N][Last];}void init(){ for (int i = 1; i <= N; ++i) { for (int j = 1; j <= Last; ++j) { dp[i][j] = 0; } }}int main(){ int T; scanf("%d", &T); while (T--) { sum = Last = 0; scanf("%d", &N); for (int i = 1; i <= N; ++i) { scanf("%d", &e[i].time); Last = max(Last, e[i].time); } for (int i = 1; i <= N; ++i) { scanf("%d", &e[i].score); sum += e[i].score; } init(); printf("%d\n", sum - DP()); } return 0;}
还有一种思路是利用贪心来做，为什么可以应用贪心规则呢？因为在这个题中，得分高的任务和得分低的都只占用1天的时间，这一天给谁不是给啊，还不如给得分高的，并把这个任务安排在限定期的最后一天。
代码如下：
#include#include #include #include #define MAXN 1005using namespace std;int N, sum, hash[MAXN];struct Node{ int time, score;}e[MAXN];bool cmp(Node a, Node b){ if (a.score != b.score) { return a.score > b.score; } else { return a.time < b.time; }}int Greedy(){ int ct, total = 0; sort(e+1, e+1+N, cmp); for (int i = 1; i <= N; ++i) { ct = e[i].time; while (hash[ct]) { --ct; // 无论如何都让这件工作做完 } if (ct > 0) { total += e[i].score; hash[ct] = 1; } } return total;}int main(){ int T; scanf("%d", &T); while (T--) { sum = 0; memset(hash, 0, sizeof (hash)); scanf("%d", &N); for (int i = 1; i <= N; ++i) { scanf("%d", &e[i].time); } for (int i = 1; i <= N; ++i) { scanf("%d", &e[i].score); sum += e[i].score; } printf("%d\n", sum - Greedy()); } return 0;}