国际大学生程序设计竞赛例题_5.4 最小值

1.题意:
s[cnt_s],t[cnt_t] cnt_t>=cnt_s.
返回t-s的绝对值和的最小值.(cnt_s个元素)
2.思路:
动态规划
d[i][j]:表示t的前j+1个数和s的前i+1个数匹配,得到的最小值.
转移方程:
d[i][j]=d[i-1]d[j-1]+abs(s[i]-t[j]); i==j
d[i][j]=min(d[i][j-1],d[i-1][j-1]+abs(s[i]-t[j])); i<j;
3.代码

#include <iostream>
#include <Algorithm>
using namespace std;

#if 0
题意:
s[cnt_s],t[cnt_t] cnt_t>=cnt_s.
返回t-s的绝对值和的最小值.(cnt_s个元素)
思路:
动态规划
d[i][j]:表示t的前j+1个数和s的前i+1个数匹配,得到的最小值.
转移方程:
d[i][j]=d[i-1]d[j-1]+abs(s[i]-t[j]); i==j
d[i][j]=min(d[i][j-1],d[i-1][j-1]+abs(s[i]-t[j])); i<j;
#endif

const int MAX=500;
int s[MAX],t[MAX];
int cnt_s,cnt_t,cnt;
int d[MAX][MAX]; //存储状态


int main()
{
    freopen("5.4.in","r",stdin);
    scanf("%d",&cnt);
    while(cnt--)
    {
        memset(d,0,sizeof(d));
        scanf("%d%d",&cnt_s,&cnt_t);
        for(int i=0;i<cnt_s;i++)
            scanf("%d",&s[i]);
        for(int i=0;i<cnt_t;i++)
            scanf("%d",&t[i]);
        sort(s,s+cnt_s);
        sort(t,t+cnt_t);
        for(int i=1;i<=cnt_s;i++)
            for(int j=i;j<=cnt_t;j++)
            {
                if(i==j) d[i][j]=d[i-1][j-1]+abs(s[i-1]-t[j-1]);
                else d[i][j]=min( d[i][j-1],d[i-1][j-1]+abs(s[i-1]-t[j-1]) );
            }
        cout<<d[cnt_s][cnt_t]<<endl;
    }

    return 0;
}

测试数据见附件.