[2010年江苏省选拔赛第三轮 第一试 挖宝藏]动态规划、离散化

【算法分析】
= =，看了解题报告才弄出来。
一开始写了个暴力的最大权闭合图骗分，结果直接崩溃。。。0分。。。Orz，也许是敲错了吧
一开始还以为容斥原理+最小割。。。
该题是动态规划。
首先我们画画图，发现它是楼梯形的。当然，如果两个宝藏y坐标相同，而x坐标差1的话，是可以成一横线的。
然后我们就可以按格子划分状态得到方程：
f[i,j]=max(f[i-1,j-1]+Sum+j,f[i-1][j]+Sum+j,f[i-1][j+1])
然后仅有在宝藏的斜线与y坐标相同的水平线上的状态才是有用的。
于是我们就只搞这些状态就可以了。
处理斜线的话，向上斜的就会x-y为定值，向下斜的就会x+y为定值，然后分别按x-y,x+y，y，排下序，最终就可以利用归并排序的思想，在本x的有效状态数的复杂度内，弄出有效的状态。
然后转移即可。
【CODE】
#include #include using namespace std;
const int N=1005;
const int maxx=10005;
const int E=1000000;
const int INF=100000000;
int n,tot[2],m,ans,X;
int list[2][E],f[2][E];
struct PT{int x,y,p,w;}a[N],b[N],c[N];

int cmp(const void *a,const void *b){
return ((PT*)a)->w-((PT*)b)->w;
}

void input(){
std::ios::sync_with_stdio(false);
tot[0]=0; tot[1]=0;
cin >> n;
for (int i=1;i<=n;i++){
cin >> a[i].x >> a[i].y >> a[i].p;
a[i].y=abs(a[i].y);
}
int ll=1,rr=1;
for (int i=1;i<=n;i++){
ll=min(ll,a[i].x-a[i].y);
rr=max(rr,a[i].x+a[i].y);
}
ll-=5; rr=rr+5-ll;
for (int i=1;i<=n;i++){
a[i].x-=ll;
b[i]=a[i];
c[i]=a[i];
}
X=rr;
for (int i=1;i<=n;i++){
a[i].w=a[i].y;
b[i].w=b[i].x+b[i].y;
c[i].w=c[i].y-c[i].x;
}
qsort(a+1,n,sizeof(PT),cmp);
qsort(b+1,n,sizeof(PT),cmp);
qsort(c+1,n,sizeof(PT),cmp);
}

void build(int x,int &tot,int *list,int *f){
tot=1;
list[1]=0;
f[1]=0; f[2]=f[3]=f[4]=-INF;
int t1=1,t2=1,t3=1,now,pos;
while (t1<=n || t2<=n || t3<=n){
now=INF; pos=0;
if (t1<=n && a[t1].w if (t2<=n && b[t2].w-x if (t3<=n && c[t3].w+x switch (pos){
case 0:for (;;);
case 1:
if (a[t1].w !=list[tot]) list[++tot]=a[t1].w;
t1++;
break;
case 2:
if (b[t2].w-x!=list[tot] && b[t2].w-x>=0) list[++tot]=b[t2].w-x;
t2++;
break;
case 3:
if (c[t3].w+x!=list[tot] && c[t3].w+x>=0) list[++tot]=c[t3].w+x;
t3++;
break;
}
}
}

void dp(int x,int &pt,int &nt,int *pl,int *nl,int *pf,int *f){
int i,j=1,k=1,Sum=0,jj;
for (i=1;i<=nt;i++){
while (k<=n && a[k].y<=nl[i]){
if (a[k].x==x) Sum+=a[k].p;
k++;
}
while (j<=pt && pl[j]+1 f[i]=-INF;
for (jj=j;jj<=j+3 && jj<=pt;jj++)
if (abs(pl[jj]-nl[i])<=1)
f[i]=max(f[i],pf[jj]+Sum-nl[i]);
}
f[1]=max(0,f[1]);
ans=max(ans,f[1]);
}

void work(){
ans=0; f[0][0]=f[0][2]=-INF;
tot[0]=1; list[0][1]=0; f[0][1]=0;
for (int i=1;i<=X;i++){
build(i,tot[i%2],list[i%2],f[i%2]);
dp(i,tot[1-i%2],tot[i%2],list[1-i%2],list[i%2],f[1-i%2],f[i%2]);
}
}

int main(){
freopen("treasures.in","r",stdin);
freopen("treasures.out","w",stdout);
input();
work();
cout << ans << endl;
return 0;
}