2015-09-21
题目大意就是这只Bessie的牛产奶很勤奋，某农民有一个时刻表，在N时间内分成M个时间段，每个时间段Bessie会一直产奶，然后有一定的效益，并且Bessie产奶后要休息两个小时。
这是一道很简答的DP，因为区间是不重复的，所以我们只要快排一下就好了，然后从第一个时间段到最后一个时间段
状态转移方程：
dp[i][j]=dp[i-1][j] j<i;
dp[i][i]=MAX(dp[i][i],dp[i][j]+list[i].eff); j<i
很简单是吧，我这道题做了两个小时？？？？
为什么？？？因为我快排写错了！
代码一开始交的时候是1001*1001矩阵，时间是0ms，但是内存要用到7000+，用滚动数组时间到16ms，但是内存变成了132，还是值得的
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX(a,b) (a)>(b)?(a):(b)
#define CUTOFF 20 typedef int Position;
typedef struct input
{
int start_hour;
int end_hour;
int eff;
}LIST; LIST list[];
long long dp1[];
long long dp2[]; void Quick_Sort(Position, Position);
void Swap(Position, Position);
void Insertion_Sort(Position, Position);
int Median_Of_Three(Position, Position, Position);
void Search(const int, const int, const int); int main(void)
{
int interval, R, N, i; while (~scanf("%d%d%d", &N, &interval, &R))
{
for (i = ; i <= interval; i++)
scanf("%d%d%d", &list[i].start_hour, &list[i].end_hour, &list[i].eff);
list[].start_hour = INT_MIN; list[].end_hour = -R;
Quick_Sort(, interval);
Search(N, interval, R);
}
return ;
} int Median_Of_Three(Position left, Position middle, Position right)
{
if (list[left].start_hour > list[middle].start_hour)
Swap(left, middle);
if (list[left].start_hour > list[right].start_hour)
Swap(left, right);
if (list[middle].start_hour > list[right].start_hour)
Swap(middle, right);
Swap(middle, right);//隐藏枢纽元
return list[right].start_hour;
} void Swap(Position x, Position y)
{
list[x].start_hour ^= list[y].start_hour;
list[y].start_hour ^= list[x].start_hour;
list[x].start_hour ^= list[y].start_hour; list[x].end_hour ^= list[y].end_hour;
list[y].end_hour ^= list[x].end_hour;
list[x].end_hour ^= list[y].end_hour; list[x].eff ^= list[y].eff;
list[y].eff ^= list[x].eff;
list[x].eff ^= list[y].eff;
} void Insertion_Sort(Position left, Position right)
{
Position i, j;
int tmp_s, tmp_e, tmp_eff;
for (i = left + ; i <= right; i++)
{
tmp_s = list[i].start_hour;
tmp_e = list[i].end_hour;
tmp_eff = list[i].eff;
for (j = i; j > left && list[j - ].start_hour > tmp_s; j--)
{
list[j].start_hour = list[j - ].start_hour;
list[j].end_hour = list[j - ].end_hour;
list[j].eff = list[j - ].eff;
}
list[j].start_hour = tmp_s;
list[j].end_hour = tmp_e;
list[j].eff = tmp_eff;
}
} void Quick_Sort(Position left, Position right)
{
Position mid = (left + right) / , i, j;
int pivot; if (right - left > CUTOFF)
{
pivot = Median_Of_Three(left, mid, right);
i = left; j = right;
while ()
{
while (list[++i].start_hour < pivot);
while (list[--j].start_hour > pivot);
if (i < j)
Swap(i, j);
else break;
}
Swap(i, right);
Quick_Sort(left, i - );
Quick_Sort(i + , right);
}
else Insertion_Sort(left, right);
} void Search(const int N, const int interval, const int R)
{
int i, j;
long long ans = -;
long long *now = dp2, *prev = dp1, *tmp = NULL; for (i = ; i <= interval; i++)
{
for (j = i - ; j >= ; j--)
{
now[j] = prev[j];
if (list[i].start_hour - list[j].end_hour >= R)
now[i] = MAX(now[i], now[j] + list[i].eff);
ans = MAX(ans, now[i]);
}
tmp = now; now = prev; prev = tmp;
}
printf("%lld\n", ans);
}