跟POJ 3042是一个类型的
思路: 先排个序 (把初始位置也插进去) f[i][j]表示从第i个到第j个之间的蛋都被收完了 f[i][j][0]表示在地点i f[i][j][1]表示在地点j 维护一个sumv数组 是v的前缀和 f[i][j][0]=max(f[i+1][j][0]-(node[i+1].x-node[i].x)*(sumv[n]-sumv[j]+sumv[i]), f[i+1][j][1]-(node[j].x-node[i].x)*(sumv[n]-sumv[j]+sumv[i])), f[i][j][1]=max(f[i][j-1][0]-(node[j].x-node[i].x)*(sumv[n]-sumv[j-1]+sumv[i-1]), f[i][j-1][1]-(node[j].x-node[j-1].x)*(sumv[n]-sumv[j-1]+sumv[i-1]));最后加上所有的y之和就好啦
注意把数组付上初值!!@某人
//By SiriusRen#include#include using namespace std;int n,x0,sumy,sumv[1005],f[1005][1005][2];struct Node{ int x,y,v;}node[1005];bool cmp(Node a,Node b){ return a.x