[BZOJ3928/4048]Outer space invaders
题目大意：
有\(n(n\le300)\)个物品，第\(i\)个物品会在\(a_i\sim b_i\)时刻出现，且离你的距离为\(d_i\)，每个时刻你可以花\(r\)的代价将离你距离\(r\)以内的物品清理掉。问清理掉所有物品的代价至少为多少？
思路：
区间DP。用\(f_{l,r}\)表示将出现时间完全包含在\(l\sim r\)之间的物品全部清理掉需要的代价，找到距离最远的物品\(h\)，则\(f_{l,r}=\min\{f_{l,k-1}+f_{k+1,r}+d_h\}(a_h\le k\le b_h)\)。
时间复杂度\(\mathcal O(n^3)\)。
源代码：
#include<vector>
#include<cstdio>
#include<cctype>
#include<climits>
#include<algorithm>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
const int N=301,logN=9;
struct Node {
int a,b,d;
};
Node node[N];
int n,f[N*2][N*2];
std::vector<int> v;
int dp(const int &l,const int &r) {
if(l>r) return 0;
int &ans=f[l][r];
if(ans!=INT_MAX) return ans;
int h=0;
for(register int i=1;i<=n;i++) {
if(node[i].a<l||node[i].b>r) continue;
if(node[i].d>node[h].d) h=i;
}
if(h==0) return ans=0;
for(register int k=node[h].a;k<=node[h].b;k++) {
ans=std::min(ans,dp(l,k-1)+dp(k+1,r)+node[h].d);
}
return ans;
}
int main() {
for(register int T=getint();T;T--) {
n=getint();
v.clear();
for(register int i=1;i<=n;i++) {
v.push_back(node[i].a=getint());
v.push_back(node[i].b=getint());
node[i].d=getint();
}
std::sort(v.begin(),v.end());
v.resize(std::unique(v.begin(),v.end())-v.begin());
const int m=v.size();
for(register int i=1;i<=n;i++) {
node[i].a=std::lower_bound(v.begin(),v.end(),node[i].a)-v.begin()+1;
node[i].b=std::lower_bound(v.begin(),v.end(),node[i].b)-v.begin()+1;
}
for(register int i=1;i<=m;i++) {
std::fill(&f[i][1],&f[i][m]+1,INT_MAX);
}
printf("%d\n",dp(1,m));
}
return 0;
}