注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj 1021  

2013-02-04 21:24:56|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

循环的债务:

这题深深的让我感觉自己多么的弱……如此基础的动规,不仅看了题解,还写了一个多小时

如果A欠B若干元B欠C若干元,那么并不需要A->B->C,而可以直接A->C并且必须这样,因为题目要求的是最小。

所以可行的转移只有6种:

A给BC B给AC C给AB

AB给C BC给A AC给B

我们可以算出刚开始每人的钱数sa,sb,sc,算出最终情况下的ea,eb,ec,设F[i][j][k]表示枚举到第i种钱,A有j元B有k元的最小花费(因为总钱数一定所以C的钱也出来了)

接下来再枚举6种情况下分别给的钱数,时间复杂度6*1000*1000*s*s(s表示当前枚举的这种钱的拥有数量),所以这是个五维的DP。

那么如何优化呢?

如果我们枚举钱的种类由小往大枚举的话,假设p=gcd(mi,mi+1,mi+2……m6)(m就是存钱数的常量数组,1,5,10,20,50,100)

如果p不能整除(ea-i)或者不能整除(eb-j)或者不能整除(ec-(sum-i-j))(也就是C的钱数),那么显然无解,可以剪去。

然后,平常动规一般两种写法,F[i][j]由什么得到或者拿F[i][j]推到什么,比如背包问题可以写成F[i][j]=F[i-1][j-v[i]]+w[i]或者F[i+1][j+v[i]]=F[i][j]+w[i],一般情况下这两者是没区别的,但这道题则不同,因为若使用第二种写法,当F[i][j]=INF(就是无解)时就可以直接剪去,不用枚举。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<ctime>
#define MAXM 1000
#define N 6
#define update(a,b) ((a)=(a)<(b)?(a):(b))
using namespace std;
const int money[]={1,5,10,20,50,100};
int F[2][3*MAXM+10][3*MAXM+10],a[N],b[N],c[N],sa,sb,sc,ea,eb,ec,sum,now;
int gcd(int a,int b){  return !b?a:gcd(b,a%b);  }
void read()
{
    int x,y,z;
    scanf("%d %d %d",&x,&y,&z);
    for(int i=N-1;i>=0;i--)
    {
        scanf("%d",&a[i]);
        sa=sa+a[i]*money[i];
    }
    for(int i=N-1;i>=0;i--)
    {
        scanf("%d",&b[i]);
        sb=sb+b[i]*money[i];
    }
    for(int i=N-1;i>=0;i--)
    {
        scanf("%d",&c[i]);
        sc=sc+c[i]*money[i];
    }
    ea=sa-x+z,eb=sb-y+x,ec=sc-z+y,sum=sa+sb+sc;
}
void Dp()
{
    for(int i=0;i<=MAXM;i++)
        for(int j=0;j<=MAXM;j++)
            F[now][i][j]=1<<30;
    F[now][sa][sb]=0;
    if(ea<0||eb<0||ec<0)
    {
        printf("impossible\n");
        return ;
    }
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<=MAXM;j++)
            for(int k=0;k<=MAXM;k++)
                F[now^1][j][k]=F[now][j][k];
        int GCD=money[i],x,y;
        for(int r=i+1;r<N;r++)
            GCD=gcd(GCD,money[r]);
        for(x=0;(ea-x)%GCD;x++);
        for(y=0;(eb-y)%GCD;y++);
        if((ec-(sum-x-y))%GCD)  continue;
        for(int j=x;j<=MAXM;j+=GCD)
        {
            if(sum-j-y<0)  break;
            for(int k=y;k<=MAXM;k+=GCD)
            {
                int vc=sum-j-k;
                if(vc<0)  break;
                if(F[now][j][k]==1<<30)  continue;
                for(int r=0;r<=a[i];r++)
                    if(j>=r*money[i])
                        for(int l=0;l<=r;l++)
                            if(k+l*money[i]<=MAXM&&vc+(r-l)*money[i]<=MAXM)
                                update(F[now^1][j-r*money[i]][k+l*money[i]],F[now][j][k]+r);
                for(int r=0;r<=b[i];r++)
                    if(k>=r*money[i])
                        for(int l=0;l<=r;l++)
                            if(j+l*money[i]<=MAXM&&vc+(r-l)*money[i]<=MAXM)
                                update(F[now^1][j+l*money[i]][k-r*money[i]],F[now][j][k]+r);
                for(int r=0;r<=c[i];r++)
                    if(vc>=r*money[i])
                        for(int l=0;l<=r;l++)
                            if(j+l*money[i]<=MAXM&&k+(r-l)*money[i]<=MAXM)
                                update(F[now^1][j+l*money[i]][k+(r-l)*money[i]],F[now][j][k]+r);
                for(int r=0;r<=a[i];r++)
                    if(j>=r*money[i])
                        for(int l=0;l<=b[i];l++)
                            if(k>=l*money[i]&&vc+(r+l)*money[i]<=MAXM)
                                update(F[now^1][j-r*money[i]][k-l*money[i]],F[now][j][k]+r+l);
                for(int r=0;r<=a[i];r++)
                    if(j>=r*money[i])
                        for(int l=0;l<=c[i];l++)
                            if(vc>=l*money[i]&&k+(r+l)*money[i]<=MAXM)
                                update(F[now^1][j-r*money[i]][k+(l+r)*money[i]],F[now][j][k]+r+l);
                for(int r=0;r<=c[i];r++)
                    if(vc>=r*money[i])
                        for(int l=0;l<=b[i];l++)
                            if(k>=l*money[i]&&j+(l+r)*money[i]<=MAXM)
                                update(F[now^1][j+(l+r)*money[i]][k-l*money[i]],F[now][j][k]+r+l);
            }
        }
        now^=1;
    }
    F[now][ea][eb]==1<<30?printf("impossible\n"):printf("%d\n",F[now][ea][eb]);
}
int main()
{
    read();
    Dp();
    return 0;
}

  评论这张
 
阅读(809)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017