http://acm.hdu.edu.cn/showproblem.php?pid=6365
细节处理
- unique返回的是最后一位的后一位，因此从1开始的数组要减去(p+1)
- 结构体可以用unqiue和lower_bound，因此结构体也可以离散化
- 此处的斜率是x/y,因为这样定义斜率会随着x的增大而增大
思路
- 一开始见到这道题，因为是个计算几何题，但是转换的思路十分巧妙：
- 首先如何处理一条线段，假设我们穿过所有点的两个端点，一定可以穿过所有线段，所以每条线段转化为两个点
- 那么如何处理每个点（x，y），因为假如斜率相同的点，都能被一条射线穿过，因此实际上衡量每个点的标准应该是他的斜率，因此将每个点转化为他的斜率
- 根据斜率将点排序，以两点之间为区间进行区间dp，每次找区间内价值最大的一条线进行区间的分割，这样只有完全包含在枚举区间内的直线才能有贡献（即假如在穿过当前直线时同时穿过的其他直线永远也不会有贡献了）
- 定义dp[i][j]为穿过包含在（i，j）区间所有直线所需要的最小代价（即穿过（i，j）区间但并不在i，j区间内的直线可能会被穿过，但是贡献在之前已经被计算了）
转移方程为
dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j]+w[k]);
#include<bits/stdc++.h>
#define M 305
#define ll long long
#define inf 1e16
using namespace std;
int n,i,T,sz;
ll h[M<<1],w[M<<1],l[M<<1],r[M<<1],dp[M<<1][M<<1];
struct N{
ll x,y;
N(){}
N(ll x,ll y): x(x),y(y){}
bool operator ==(const N& rhp)const{
return x*rhp.y-y*rhp.x==0;
}
bool operator<(const N& rhp)const{
return x*rhp.y-y*rhp.x<0;
}
}p[M<<1];
int id(N a){ return lower_bound(p+1,p+1+sz,a)-p;}
ll dfs(int L,int R){
ll &ans=dp[L][R];
if(L>R)return 0;
if(ans!=-1)return ans;
ans=0;
ll ma=-1,x;
for(int i=1;i<=n;i++){
if(L<=l[i]&&r[i]<=R){
if(w[i]>ma){
ma=w[i];x=i;
}
}
}
if(ma==-1)return ans;
ans=inf;
for(int i=l[x];i<=r[x];i++){
ans=min(ans,dfs(L,i-1)+dfs(i+1,R)+ma);
}
return ans;
}
int main(){
scanf("%d",&T);
while(T--){
memset(dp,-1,sizeof(dp));
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%lld%lld%lld%lld",&h[i],&l[i],&r[i],&w[i]);
p[2*i-1]=N(l[i],h[i]);
p[2*i]=N(r[i],h[i]);
}
sort(p+1,p+1+2*n);
sz=unique(p+1,p+2*n+1)-p-1;
for(i=1;i<=n;i++){
l[i]=id(N(l[i],h[i]));
r[i]=id(N(r[i],h[i]));
}
printf("%lld
",dfs(1,sz));
}
}