CF 351A - Jeff and Rounding DP

http://codeforces.com/problemset/problem/351/C

题意：有2*n个浮点数a₁,a₂,a₃...a_2*n，把他们分成n队，对于每对<A,B>，对A做floor() 操作，对B 做ceil()操作。生成b_1...b_2*n,求|(b₁+b₂+...+b_2*n)-(a₁+a₂+a₃...+a_2*n)|的最小值。

对于每个数a_i，对他们做floor（）的cost是up()=ai-floor(ai) ,做ceil()的cost是down()=ceil(ai)-ai

设f[i][j]表示前i个节点有j个做ceil()操作(i-j个floor())的最优值

　　f[i][j]=min{f[i-1][j-1]+up(a[i]), 对ai做up()的代价

　　　　　　　　f[i-1][j]+down(a[i])} 对ai做down()的代价、

当i == j时注意f[i-1][j]不存在这种情况.

这里的min{}里面比较的是绝对值。、

临界值f[0][0]=0; f[0][1]=0;目标答案|f[2*n][n]|。

#include <stdio.h>

#include <string.h>

#include <math.h>

#define N 2001

double min(double a,double b)

{

    return fabs(a)>fabs(b)? b:a;

}

double up(double x)

{

    return ceil(x)-x;

}

double down(double x)

{

    return x-floor(x);

}

double a[*N+];

double f[*N+][N+];

int main()

{

    int i,j,m,n;

    while (scanf("%d",&n)!=EOF)

    {

        for (i=;i <=*n; i++)

            scanf("%lf",&a[i]);

        f[][]=;

        f[][]=;

       double tmp;

        for (i=;i<=*n; i++)

            for (j=; j<= n && j<=i;j++)

            {

                tmp=;

                if (i>j) tmp=f[i-][j]+down(a[i]);

                if (j>)

                    tmp=min(tmp,f[i-][j-]-up(a[i]));

                    f[i][j]=tmp;

            }

            printf("%0.3lf\n",fabs(f[*n][n]));

    }

    return ;

}

好吧，其实仔细看看就是一个背包。

我们可以把i 这个维度，在空间上优化点。跟0/1背包似的。

f[j]=min{f[j-1]+up(a[i]),f[j]+down(a[i])}

不过j循环得downto了，因为f[j-1]在迭代前，还应该是f[i-1][j-1]这个状态，而不是f[i][j-1]了。

#include <stdio.h>

#include <string.h>

#include <math.h>

#define N 2001

//#define min(a,b) a>b?b:a

double min(double a,double b)

{

    return fabs(a)>fabs(b)? b:a;

}

double up(double x)

{

    return ceil(x)-x;

}

double down(double x)

{

    return x-floor(x);

}

double a[*N+];

double f[N+];

int main()

{

    int i,j,m,n;

    while (scanf("%d",&n)!=EOF)

    {

        for (i=;i <=*n; i++)

            scanf("%lf",&a[i]);

        f[]=; f[]=;

       double tmp;

        for (i=;i<=*n; i++)

            for (j=min(i,n);j>=;j--)

            {

                tmp=;

                if (i>j) tmp=f[j]+down(a[i]);

                if (j>)

                    tmp=min(tmp,f[j-]-up(a[i]));

                    f[j]=tmp;

                //f[i][j]=min(f[i-1][j-1]+up(a[i]),f[i-1][j]+down(a[i]));

            }

            printf("%0.3lf\n",fabs(f[n]));

    }

    return ;

}

巴特西

CF 351A - Jeff and Rounding DP

最新文章

热门文章