周末作业20170515

题解

B - XHXJ's LIS（HDU 4352）
题目详情
题目大意：

求L到R的上升序列长度为k的数的个数

解题思路：

用LIS求上升序列，用数位dp求一个数的上升序列等于k的个数，用位运算（压缩状态）求一个数中含有的上升序列数目的个数（因为K最多为10）

AC代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;
LL L,R,K,dp[35][1<<10][15];

int bit[35];
int instead(int st,int x){//找到适合它的位置放下
    for(int i=x;i<10;i++)
        if(st&(1<<i))  return ((st^(1<<i))|(1<<x));//先将原来那个数清除，再加上当前数
    return st|(1<<x);
}
int getlen(int st){//求这个数中上升序列的长度（位运算）
    int cnt=0;
    while(st){
        if(st&1) cnt++;
        st>>=1;
    }
    return cnt;
}
> LL dfs(int len,int st,int zero,int f){//zero判断前面的个数字是否存在非0. f表示判断前一位是否是上界
    if(len==0){
        if(getlen(st)==K)
            return 1;
        else return 0;
    }
    if(f&&dp[len][st][K]!=-1) return dp[len][st][K];//表示长度为len，状态为st（上升序列中各数的和），长度为k的个数
    LL ans=0;
    int last=f?9:bit[len];
    for(int i=0;i<=last;i++)
        ans+=dfs(len-1,(zero==0&&i==0)?0:instead(st,i),zero||i,f||(i<last));
    if(f) dp[len][st][K]=ans;
    return ans;
}
LL getans(LL n){
    int len =0;
    while(n){
        bit[++len]=n%10;
        n/=10;
    }
    return dfs(len,0,0,0);
}
int main(){
    int T,ncase=0;
    scanf("%d",&T);
    memset(dp,-1,sizeof(dp));
    while(T--){
        scanf("%lld%lld%lld",&L,&R,&K);
        printf("Case #%d: %lld\n",++ncase,getans(R)-getans(L-1));
    }
    return 0;
}

C - Brackets Sequence（POJ1141）
题目详情

题目大意：

给出一个关于‘（’ ，‘）’,'[' ,']'的序列，求出以此为子序列的最短合法序列

解题思路：

这是一道区间dp题，用dp[i][j]表示i~j区间需要添加的个数，dp[i][i]=1;
如果s[i]和是s[j]能配对，那么 dp[i][j]=dp[i+1][j-1];否则dp[i][j]=min(dp[i][k],dp[k+1][j])i+1<=k c[i][j]则用来记录他们最佳断点k的位置，如果s[i]和是s[j]能配对，s[i
][j]=-1;
AC代码：

#include <cstring>
#include <algorithm>
#include <string>

using namespace std;
int dp[105][105],c[105][105],len;
string s;

void init(){
    int m;
    for(int i=0;i<len;i++)
        dp[i][i]=1;
    for(int l=1;l<len;l++){//长度遍历
        for(int i=0;i+l<len;i++){//当前长度的起点
            int j=i+l;
            m=dp[i][i]+dp[i+1][j];
            c[i][j]=i;
            for(int k=i+1;k<j;k++){
                if(dp[i][k]+dp[k+1][j]<m){
                    m=dp[i][k]+dp[k+1][j];
                    c[i][j]=k;
                }
            }
            dp[i][j]=m;
            if((s[i]=='('&&s[j]==')')||(s[i]=='['&&s[j]==']')){//能配对
                if(dp[i+1][j-1]<m){
                    dp[i][j]=dp[i+1][j-1];
                    c[i][j]=-1;
                }
            }
        }
    }
}
void dfs(int i,int j){//递归输出
    if(i>j) return ;
    if(i==j){//相等时则自己配一个
        if(s[i]=='('||s[i]==')') cout<<"()";
        else cout<<"[]";
    }
    else {
        if(c[i][j]==-1){
            if(s[i]=='('){
               cout<<"(";
               dfs(i+1,j-1);
               cout<<")";
            }
            else {
                cout<<"[";
                dfs(i+1,j-1);
                cout<<"]";
            }
        }
        else {
            dfs(i,c[i][j]);
            dfs(c[i][j]+1,j);
        }
    }
}
int main(){
    memset(c,-1,sizeof(c));
    cin>>s;
    len=s.length();
    init();
    dfs(0,len-1);
    cout<<endl;
    return 0;
}

E - Little Elephant and Elections（codefores258B）
题目详情

题目大意：

4和7位路lucky数，从1~m中选出一个数，再选出6个数，严格要求第一个数的幸运值大于其余6个数之和（3447幸运值为3）

解题思路：

并没要求求具体的数，所以我们只需求出1~m中幸运值为1,2,3，，，分别有多少个即可，可用数位dp完成。然后在求满足条件的方案数（详情见代码）

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;
LL dp[15][15],ans,bit[15],lucky[15];
int cnt;
#define mod 1000000007

void DFS(LL now,LL Max,LL number,LL cur){//now表示当前6个数（可能还没选完）的幸运值和，max表示先选出来的那个数的幸运值，number表示选了几个数，cur表示当前方案数
    if(now>=Max) return ;
    if(number==7) {
        ans=(ans+cur)%mod;
        return ;
    }
    for(int i=0;i<cnt;i++){
        if(lucky[i]){
            lucky[i]--;//先减掉一个数，表示选中这个数
            DFS(now+i,Max,number+1,cur*(lucky[i]+1)%mod);//lucky[i]+1是因为刚才减掉了一个，选一个幸运值为i的数共有lucky[i](减掉之前）
            lucky[i]++;//再加上
        }
    }
}
LL dfs(int pos,int res,bool limit){
    LL sum=0;
    if(pos==0) return res==0;
    if(!limit&&dp[pos][res]!=-1) return dp[pos][res];//表示pos位数，幸运数为res的个数
    int last=limit?bit[pos]:9;
    for(int i=0;i<=last;i++)
        sum+=dfs(pos-1,res-(i==4||i==7),limit&&(i==last));
    if(!limit) dp[pos][res]=sum;
    return sum;
}
void getbit(LL m){
    cnt=0;
    while(m){
        bit[++cnt]=m%10;
        m/=10;
    }
}
int main(){
    memset(dp,-1,sizeof(dp));
    LL m;
    scanf("%lld",&m);
    getbit(m);
    for(int i=0;i<=cnt;i++)
        lucky[i]=dfs(cnt,i,1);
    lucky[0]--;
    for(int i=1;i<=cnt;i++)
        DFS(0,i,1,lucky[i]);
    printf("%lld",ans);
    return 0;
}

F - Mondriaan's Dream (POJ 2144)

题目详情

题目大意：

轮廓线dp，一个n*m的矩阵，用1*2的方块铺满，问有多少种方案

解题思路：

这里规定两种放置方法，只能上方（方块属于下面的方格），右放（方块属于左边的方格）；用dp[i][s]表示在第i行为s的状态下（前i-1行全部放满）状态转移为dp[i][s]=sum(dp[i-1][ss]),这里的ss是跟s兼容的（详见代码）

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int n,m,maxn;
typedef long long LL;
LL ans[15][15],dp[15][(1<<11)-1];

bool judge(int s){//判断第一行的状态是否合法
    int j=0;
    while(j<m){
        if(s&(1<<j)){//如果第j列为1，因为不能只能右放和上放，那么下一列也必定为1
            if(j==m-1) return false ;
            if(!(s&(1<<(j+1)))) return false ;
            j+=2;
        }
        else j++;//为0时直接考虑下一列，因为第二行可以来填充此处
    }
    return true;
}
bool ok(int s,int ss){//判断s和ss是否兼容
    int j=0;

    while(j<m){
        if(s&(1<<j)){//如果第i行的第j列为1，并且i-1行的第j列也为1的话，那么第i行j列只能横放，并且第i-1行j+1列也必须为1（否则因为规定的放置方法，会无法放）
            if(ss&(1<<j)){
                if(j<m-1&&(s&(1<<(j+1)))&&(ss&(1<<(j+1))))
                    j+=2;
            else return false ;
            }
            else j++;//如果i-1行的j列为0，那么就直接上放就ok
        }
        else {//i行j列为0时说明i+1行可以满足它，那么i-1行的j列就必须为1，否则在接下来就一直无法放置
            if(ss&(1<<j)) j++;
            else return false ;
        }
    }
    return true;
}
LL solve(){
    memset(dp,0,sizeof(dp));
    maxn=(1<<m);
    for(int s=0;s<maxn;s++){//先判断出合法的第一行
        if(judge(s))
            dp[1][s]=1;
    }
    for(int r=2;r<=n;r++){//从第二行开始dp
        for(int s=0;s<maxn;s++)
            for(int ss=0;ss<maxn;ss++)
                if(ok(s,ss)) dp[r][s]+=dp[r-1][ss];
    }
    return ans[n][m]=dp[n][maxn-1];
}
int main(){
    while(~scanf("%d%d",&n,&m)){
        if(n==0&&m==0) break;
        else if((n*m)&1)  printf("0\n");
        else  {
            if(n<m) swap(n,m);
            if(!ans[n][m]) solve();
            printf("%lld\n",ans[n][m]);
        }
    }
    return 0;
}