SRM 554 DIV2

250pt

题意：

给定两个整数以及它们的个数，求由多少个整数由它们组成的，且两个数的个数差不超过1。

 

分析：

暴力枚举。

 

class TheBrickTowerEasyDivTwo 
{ 
        public: 
        int find(int n, int a, int m, int b) 
        { 
            int i,j,k;
            bool dp[10000]={false};
            for(i=0;i<=n;i++)
                for(j=max(i-1,0);j<=i+1;j++)
                if(j<=m){
                        dp[i*a+j*b]=true;
                }
            for(i=1,k=0;i<10000;i++)
                if(dp[i])
                    k++;
            return k;
        } 
        

 
}; 

 

 

500pt:

题意：

有n座高度为h[i]的塔，当塔倒下时为了不碰到相邻的塔，它们之间的距离取max(h[i],h[i-1],h[i+1]),重新排列塔的顺序，使第1座塔距第n座塔最短。

 

分析：

因为n<=7,直接DFS暴力枚举全排列。

 

class TheBrickTowerMediumDivTwo 
{ 
        public: 
        int vis[8];
        int n,ans;
        vector <int> c;
        void DFS(int i,int k,vector <int> a)
        {
            int j;
            vis[i]=k;
            if(k>=n-1)
            {
                int b[9],tmp=0;
                for(j=0;j<n;j++)
                    b[vis[j]]=j;
                for(j=1;j<n;j++)
                    tmp+=max(a[b[j]],a[b[j-1]]);
                if(tmp<ans)
                {
                    ans=tmp;
                    c.clear();
                    for(j=0;j<n;j++)
                        c.push_back(b[j]);
                }
                vis[i]=-1;
                return ;
            }
            for(j=0;j<n;j++)
                if(vis[j]==-1)
                    DFS(j,k+1,a);
            vis[i]=-1;
        }
        vector <int> find(vector <int> a) 
        { 
            n=a.size();
            memset(vis,-1,sizeof(vis));
            ans=1000000;
            for(int i=0;i<n;i++)
                DFS(i,0,a);
            return c;
        } 
        
 
}; 

 

 

1000pt:

题意：

给定四个有C种颜色的1*1*1的小方块组成2*2*1的大方块，由这种方块组成塔，给定塔的最高层数H，小方块的颜色数C，至多有K个相邻（有共同面）的小方块颜色相同，求塔的总数。

 

分析：

一看就是动态规划，只是担心状态数太多会超时，写起来又麻烦。

后来用状态压缩表示大方块就好写多了，dp[i][j][k]表示第i层大方块状态为j(0<=j<4^4)且有k种相邻颜色时有多少种。

O(4e7)都不超时，100多ms

 

unsigned dp[48][256][9];

class TheBrickTowerHardDivTwo 
{ 
        public: 
        int find(int C, int K, int H) 
        { 
            int i,j,k,t,u,v,n=H,m=K,a[333][333],b[6],w[333],s=C*C*C*C;
            const int MOD=1234567891;
            for(k=0;k<s;k++)
            {
                w[k]=0;
                for(i=0,t=k;i<4;i++,t/=C)
                    b[i]=t%C;
                for(i=0;i<4;i++)
                    if(b[i]==b[(i+1)%4])
                        w[k]++;
            }
            for(i=0;i<s;i++)
                for(j=i;j<s;j++)
                {
                    a[i][j]=0;
                    int ti=i,tj=j;
                    for(k=0;k<4;k++,ti/=C,tj/=C)
                        if(ti%C==tj%C)
                            a[i][j]++;
                    a[j][i]=a[i][j];
                }
            memset(dp,0,sizeof(dp));
            for(j=0;j<s;j++)
                dp[0][j][w[j]]=1;

            for(i=0;i+1<n;i++)
                for(u=0;u<s;u++)
                    for(k=0;k<=m;k++)
                        if(dp[i][u][k])
                            for(v=0;v<s;v++)
                                if(k+w[v]+a[u][v]<=m)
                                    dp[i+1][v][k+w[v]+a[u][v]]=(dp[i+1][v][k+w[v]+a[u][v]]+dp[i][u][k])%MOD;
            unsigned ret=0;
            for(i=0;i<n;i++)
                for(j=0;j<s;j++)
                    for(k=0;k<=m;k++)
                        ret=(ret+dp[i][j][k])%MOD;
            return ret;
        } 
        

};