首页 > 其他 > 详细

[SCOI2013]火柴棍数字(背包)

时间:2019-03-16 10:25:46      阅读:26      评论:0      收藏:0      [点我收藏+]

标签:数字   +=   cstring   turn   i++   是否   ons   我们   str   

题目

做饭

由于越高位越好,我们先得出能组成的最高位

\(f[i][j][k]\)表示从低到高位第\(i\)位,手里拿着\(j\)根火柴,第\(i\)位是否为\(0\)所需要的最少火柴

我们转移仅需得出移动,与多余或需添的映射关系;然后枚举变化关系去转移

得出最高位后,直接贪心看目前所在最高位是否能添某个数字(最大)

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=3510;
int n,m,all,use,len,i,j,k,x;char a[N];
short f[N/2][N*2][2];
int S[10]={126,48,107,121,53,93,95,112,127,125},dx[11][10],dy[11][10];
inline void up(short&x,short y){if(x>y)x=y;}
int main(){
    for(i=0;i<10;i++)
        for(j=0;j<10;j++)
            for(k=0;k<7;k++){
                if(!(S[i]>>k&1)&&(S[j]>>k&1))
                    dx[i][j]++,dy[i][j]++;//dy:remove dx:increase
                if((S[i]>>k&1)&&!(S[j]>>k&1))
                    dx[i][j]--;
            }
    for(i=0;i<10;i++)
        for(k=0;k<7;k++)
            if(S[i]>>k&1)
                dx[10][i]++,dy[10][i]++;
    scanf("%s%d",a+1,&m);
    n=strlen(a+1);
    reverse(a+1,a+n+1);//最低位排前面 
    for(i=1;i<=n;i++)
        a[i]-='0';
    for(i=1;i<=n;i++)
        all+=dy[10][a[i]];//总火柴 
    len=all/2;
    for(i=n+1;i<=len;i++)
        a[i]=10;
    for(i=0;i<=len;i++)
        for(j=-m;j<=m;j++)
            for(k=0;k<2;k++)
                f[i][j+N][k]=m+1;
    f[0][N][0]=0;//N:0
    for(i=0;i<len;i++)
        for(j=-m;j<=m;j++)
            for(k=0;k<2;k++)
                if(f[i][j+N][k]<=m)
                    for(x=0;x<10;x++){
                        up(f[i+1][j+N+dx[a[i+1]][x]][x==0],
                            f[i][j+N][k]+dy[a[i+1]][x]);
                    }
    while(f[len][N][0]>m)len--;//最长长度 
    for(i=0;i<=len;i++)
        for(j=-m;j<=m;j++)
            up(f[i][j+N][0],f[i][j+N][1]);
    for(all=0,i=len;i;i--)
        for(j=9;~j;j--){
            all+=dx[a[i]][j],
            use+=dy[a[i]][j];
            if(f[i-1][N-all][0]<=m-use){
                printf("%d",j);break;
            }
            all-=dx[a[i]][j],use-=dy[a[i]][j];
        }
    return 0;
}

[SCOI2013]火柴棍数字(背包)

标签:数字   +=   cstring   turn   i++   是否   ons   我们   str   

原文:https://www.cnblogs.com/y2823774827y/p/10540547.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号