poj 3375 Network Connection(dp 최적화)

Network Connection
Time Limit: 1000MS
 
Memory Limit: 65536K
Total Submissions: 3126
 
Accepted: 686
Description
There are M network interfaces in the wall of aisle of library. And N computers next to the wall need to be connected to the network. A network interface can only connect with one computer at most. To connect an interface with coordinate x with a computer with coordinate y needs |x - y| unit of length of network cable. Your task is to minimize the total length of network cables to be used.
Input
The first line contains two integers M (1 ≤ M ≤ 100000), N (1 ≤ N ≤ 2000, N ≤ M). The following M + N lines each contains a integer coordinate. The first M coordinates are corresponding to the network interfaces, and the next N ones corresponding to the computers. All coordinates are arranged in [0, 1000000]. Distinct interfaces may have the same coordinate, so do the computers.
Output
Print an integer, representing minimum length of network cables to be used.
Sample Input

4 2
1
10
12
20
11
15

Sample Output

4

Source
POJ Monthly--2007.09.09, Updog
제목:
m개의 인터페이스(m<=100000), n대의 컴퓨터(n<=2000)가 있는데 각 컴퓨터는 하나의 인터페이스에 대응하고 한 인터페이스는 한 대의 컴퓨터만 수용할 수 있다. 컴퓨터 X가 인터페이스 Y에 연결되면 배선 길이는 |X-Y|로 모든 컴퓨터를 배치하여 최소한의 배선 길이를 구해야 한다.
아이디어:
dp[i][j]는 전 i대 컴퓨터가 전 j개 인터페이스에 연결하는 데 필요한 최소 비용을 표시하고 상태 이동 방정식이 있음을 나타낸다.
dp[i][j]=min(dp[i][j-1],dp[i-1][j-1]+abs(a[i]-b[j]));
복잡도는 O(n*m)이므로 최적화가 필요합니다.
a[i]가 b[]수 그룹의 위치pos를 찾으면 i에 대응하는 인터페이스가 있는 구간 범위가 [pos-n,pos+n]이면 복잡도가 O(n*n)로 낮아진다.
공간이 열리지 않으면 스크롤 그룹을 사용해야 한다. 그리고 주의해야 할 것은 상태가 이동할 때 상황을 나누어야 한다. 현재 상태가 나타나야만 현재 상태로 이동할 수 있다.
사고방식: cms 블로그
코드:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
//#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 2005
#define MAXN 100005
#define mod 1000000000
#define INF 0x3f3f3f3f
using namespace std;

int n,m,ans,flag;
int a[maxn],b[MAXN],pos[maxn];
int dp[2][MAXN];

void presolve()
{
    int i,j;
    sort(a+1,a+n+1);
    sort(b+1,b+m+1);
    for(i=1;i<=n;i++)  //    a[i] b[]    
    {
        pos[i]=lower_bound(b+1,b+m+1,a[i])-b;
    }
}
void solve()
{
    int i,j,p=1,s,e,ps,pe;
    for(i=0;i<=m;i++)
    {
        dp[0][i]=0;
        dp[1][i]=INF;
    }
    ps=0,pe=m;
    for(i=1;i<=n;i++)
    {
        s=max(i,pos[i]-n-1);  //      i  
        e=min(pos[i]+n+1,m);
        dp[p][s-1]=INF;       //         INF
        for(j=s;j<=e;j++)
        {
            if(j<=pe+1) dp[p][j]=min(dp[p][j-1],dp[p^1][j-1]+abs(a[i]-b[j]));//  j-1             j-1     
            else dp[p][j]=min(dp[p][j-1],dp[p^1][pe]+abs(a[i]-b[j]));//            dp[p^1][pe]  
        }
        ps=s,pe=e;
        p=p^1;
    }
    ans=dp[p^1][e];
}
int main()
{
    int i,j,t;
    while(~scanf("%d%d",&m,&n))
    {
        for(i=1;i<=m;i++)
        {
            scanf("%d",&b[i]);
        }
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        presolve();
        solve();
        printf("%d
",ans);
    }
    return 0;
}