|
|
思路： 這題數據很水，所以二維背包都能過的。
 #include <stdio.h>
#include <stdlib.h>
#define MAX_N 10032
#define MAX_B 1024
#define MAX_L 1024
  struct node  {
 int x, w, f, c;
 };
struct node in[MAX_N];
int dp[MAX_L][MAX_B], right[MAX_L];
int L, N, B;
int cmp(const void *a, const void *b)
{
return ((struct node *)a)->x - ((struct node *)b)->x;
}
inline void update_max(int *a, int b)
{
if (b > *a)
*a = b;
}
int main()
{
int i, c;
struct node *t;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d%d", &L, &N, &B);
for (i = 0; i < N; i++)
scanf("%d%d%d%d", &in[i].x, &in[i].w, &in[i].f, &in[i].c);
qsort(in, N, sizeof(in[0]), cmp);
right[0] = 1;
dp[0][0] = 1;
  for (i = 0; i < N; i++) {
t = &in[i];
for (c = 0; c < right[t->x] && c + t->c <= B; c++) {
if (!dp[t->x][c])
continue;
update_max(&dp[t->x + t->w][c + t->c], dp[t->x][c] + t->f);
update_max(&right[t->x + t->w], c + t->c + 1);
 }
}
for (i = c = 0; c <= B; c++)
update_max(&i, dp[L][c]);
printf("%d\n", i - 1);
return 0;
}
|