[POJ3375 Network Connection & 衡阳八中1980]去除冗余状态优化的动态规划

【题目链接】
http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1980 （中文）
http://acm.pku.edu.cn/JudgeOnline/problem?id=3375
【算法分析】
初看题目。。以为费用流。然后看规模，果断dp。
去除无用状态以后就能AC。
当然，一开始果断排序。
然后，容易用F[i][j]表示选完A[i]和B那边选过B[j]时最小值是多少。
实际上容易发现，令Best[i]为abs(A[i]-B[j])得到最小值时的位置。
那么他最多向前让n-i位（因为他后面还有n-i个数要配），或者说向后让i-1位。
所以，对于每个A[i]，只要储存[Best[i]-(n-1),Best[i]+(i-1)]这个区间上的F值就可以了。
于是能在规定时限内很快通过。
【时间复杂度】O(n lg n + m lg m + n^2)
【空间复杂度】O(n^2 + m) 滚动可以变成O(n + m)
【其它】WA了几次，因为算Best的时候，没有考虑到B数组相等，一直卡在那里的情况= =。。。
【CODE】
#include #include #include #define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
const int M=1000005;
const int N=2005;
const int INF=0x7FFFFFFF;
int n,m;
int a[N],b[M],St[N];
int F[N][N];

void Read(int &x){
char ch=getchar();
while (ch==’ ‘ || ch==’n’) ch=getchar();
int sign=1;
if (ch==’-‘){
sign=-1;
ch=getchar();
while (ch==’ ‘ || ch==’n’) ch=getchar();
}
x=0;
while (ch>=’0′ && ch<='9'){
x=x*10+ch-‘0’;
ch=getchar();
}
x*=sign;
}

void input(){
Read(m); Read(n);
for (int i=1;i<=m;i++) Read(b[i]);
for (int i=1;i<=n;i++) Read(a[i]);
}

int cmp(const void *A,const void *B){return (*((int*)A))-(*((int*)B));}
void init(){
qsort(a+1,n,sizeof(int),cmp);
qsort(b+1,m,sizeof(int),cmp);
int i,j=1;
for (i=1;i<=n;i++){
while (j St[i]=max(1,j-(n-i));
}
}

void dp(){
int i,j,k,ans=INF;
if (n==1){
for (i=1;i<=m;i++) ans=min(ans,abs(a[1]-b[i]));
printf("%dn",ans);
return;
}
F[1][0]=abs(a[1]-b[St[1]]);
for (i=1;St[1]+i<=m && i<=n;i++)
F[1][i]=min(F[1][i-1],abs(a[1]-b[St[1]+i]));
for (i=2;i<=n;i++){
k=St[i-1];
for (j=St[i];j<=m && j<=St[i]+n;j++){
while (k int &t=F[i][j-St[i]];
t=INF;
if (j!=St[i]) t=F[i][j-St[i]-1];
t=min(t,F[i-1][k-St[i-1]]+abs(a[i]-b[j]));
if (i==n) ans=min(ans,t);
}
}
printf("%dn",ans);
}

int main(){
input();
init();
dp();
}