常规(优化)dp-poj-3375-Network Connection
题目链接：
http://poj.org/problem?id=3375
题目大意：
有m个接口（m<=100000），n台电脑（n<=2000），每台电脑对应一个接口，一个接口只能容纳一台电脑，电脑X如果连到接口Y，则需布线长度为|X-Y},将所有的电脑布好，求最小的布线长度。
解题思路：
贪心优化dp.
显然不交叉比交叉更好。
dp[i][j]表示前i台电脑布到前j个接口所需的最小长度。dp[i][j]=min(dp[i-1][j-1]+abs(B[i]-A[j]),dp[i][j-1]),但直接这样求时间复杂度为O(nm),会超时。需要优化,能否优化到o(n^2) 可以求出最靠近B[i]的A中的p，显然与B[i]对应的接口肯定在p-n~p+n之间，前面的最多只能占用n个，所以对每台电脑i,找到最接近的位置p,然后只用更新p-n~p+n.
代码：
#include<iostream>#include<cmath>#include<cstdio>#include<sstream>#include<cstdlib>#include<string>#include<cstring>#include<algorithm>#include<vector>#include<map>#include<set>#include<stack>#include<list>#include<queue>#include<ctime>#include<bitset>#define eps 1e-6#define INF 0x3f3f3f3f#define PI acos(-1.0)#define ll __int64#define LL long long#define lson l,m,(rt<<1)#define rson m+1,r,(rt<<1)|1#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;#define Maxm 110000#define Maxn 2100int n,m;int A[Maxm],B[Maxn];int dp[2][Maxm]; //dp[i][j]表示前i台电脑安排到前j个接口最小值int main(){ while(~scanf("%d%d",&m,&n)) { for(int i=1;i<=m;i++) scanf("%d",&A[i]); for(int i=1;i<=n;i++) scanf("%d",&B[i]); sort(A+1,A+m+1); sort(B+1,B+n+1); for(int i=0;i<=m;i++) dp[0][i]=0; int pp=1,sta=0; int s1=1,e1=m,s2,e2; for(int i=1;i<=n;i++) { int cur=sta^1; for(;pp<=m&&A[pp]<B[i];pp++); //找到第一个不小于B[i]的 总的复杂度o(m) s2=max(i,pp-n); //第i台电脑能够放的最开始的位置 e2=min(m,pp+n);//最后的位置 dp[cur][s2-1]=INF; //初始无效状态 for(int j=s2;j<=e2;j++) //枚举第i台电脑可能对应的接口 { if(j>=s1&&j<=e1) //如果在前一台电脑的 范围内，可以根据前一状态来， dp[cur][j]=min(dp[sta][j-1]+abs(A[j]-B[i]),dp[cur][j-1]); else //如果不在的话 根据前一台电脑的最后状态来 这样就跳过了中间的很多无关的状态 dp[cur][j]=min(dp[sta][e1]+abs(A[j]-B[i]),dp[cur][j-1]); } s1=s2,e1=e2; sta=cur; } printf("%d\n",dp[sta][m]); } return 0;}