[关闭]
@morehigh 2017-05-27T15:45:02.000000Z 字数 3213 阅读 1001

CQUPT DP 2017/5/15

DP

B - XHXJ's LIS HDU - 4352 

  1. 输入的L,R,K.(0<L<=R<2^63-1 and 1<=K<=10),表示一个数字拆分成位数（个，十，百。。）满足长度为K的递增的序列，求出从L到R的满足条件的数字的个数。
  1. 数位dp+状态压缩，dp[pos][st][k]=ans，表示位数为pos，状态为st，上升子序列长度为k的个数为ans，其中用到位运算是为了解决上升序列状态，然后根据状态中1的个数可以算出上升序列的长度。
  1. #include <bits/stdc++.h>
  3. using namespace std;
  4. typedef long long ll;
  5. ll dp[50][1<<10][15];
  6. ll l,r,k;
  7. ll a[50];
  8. int getst(int st,int x)
  9. {
  10.      for(int i=x;i<10;i++)
  11.         if(st&(1<<i)) return ((st^(1<<i))|(1<<x));
  12.     return st|(1<<x);
  13. }
  14. ll getlen(int st)
  15. {
  16.     int cnt=0;
  17.     while(st)
  18.     {
  19.         if(st&1) cnt++;
  20.         st>>=1;
  21.     }
  22.     return cnt;
  23. }
  24. ll dfs(int pos,int st,int zero,int f)
  25. {
  26.     if(pos<1) return getlen(st)==k;
  27.     if(!f&&dp[pos][st][k]!=-1) return dp[pos][st][k];
  28.     int las= f?a[pos]:9;
  29.     ll ans=0;
  30.     for(int i=0;i<=las;i++)
  31.     {
  32.         ans+=dfs(pos-1,(zero==0&&i==0)?0:getst(st,i),zero||i,f&&(i==las));
  33.     }
  34.      if(!f) dp[pos][st][k]=ans;
  35.     return ans;
  36. }
  37. ll sol(ll x)
  38. {
  39.     int len=0;
  40.     while(x)
  41.     {
  42.         a[++len]=x%10;
  43.         x/=10;
  44.     }
  45.     return dfs(len,0,0,1);
  46. }
  48. int main()
  49. {
  50.     int t,cas=1;
  51.     scanf("%d",&t);
  52.     memset(dp,-1,sizeof(dp));
  53.     while(t--)
  54.     {
  55.         scanf("%lld%lld%lld",&l,&r,&k);
  56.         printf("Case #%d: %lld\n",cas++,sol(r)-sol(l-1));
  57.     }
  58.     return 0;
  59. }

C - Brackets Sequence POJ - 1141

  1. 左右括号匹配问题，给出一串字符，求出最少添加多少个括号，能使全部括号匹配，满足条件。
  1. d[i][j]表示在区间i到j中有最少加多少个括号使得全部括号达到匹配，c[i][j]表示在i，j中添加括号的位置，d[i][j]=min(d[i][j],d[i][k]+d[k+1][j]);
  2.  if(ss[i]=='('&&ss[j]==')'||ss[i]=='['&&ss[j]==']')   d[i][j]=d[i+1][j-1]; 区间i，j暂时不用插入括号。
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <string>
  5. #include <algorithm>
  7. using namespace std;
  8. string ss;
  9. int len;
  10. int d[100][100];
  11. int c[100][100];
  12. void sol()
  13. {
  14.     int mn,j;
  15.     memset(d,0,sizeof(d));
  16.     for(int i=0;i<len;i++) d[i][i]=1;
  17.     for(int l=1;l<len;l++)
  18.     {
  19.         for(int i=0;i+l<len;i++)
  20.         {
  21.             j=i+l;
  22.             d[i][j]= 0x7fffffff;
  24.             for(int k=i;k<j;k++)
  25.             {
  26.                 if(d[i][k]+d[k+1][j]<d[i][j])
  27.                 {
  28.                     d[i][j]=d[i][k]+d[k+1][j];
  29.                     c[i][j]=k;
  30.                 }
  31.             }
  32.           //  d[i][j]=mn;
  33.             if(ss[i]=='('&&ss[j]==')'||ss[i]=='['&&ss[j]==']')
  34.             {
  35.                 if(d[i+1][j-1]<d[i][j])
  36.                 {
  37.                     d[i][j]=d[i+1][j-1];
  38.                     c[i][j]=-1;
  39.                 }
  40.             }
  41.         }
  42.     }
  43. }
  44. void print(int i,int j)
  45. {
  46.     if(i>j) return ;
  47.     if(i==j)
  48.     {
  49.         if(ss[i]=='('||ss[i]==')') cout<<"()";
  50.         else  cout<<"[]";
  51.     }else{
  52.         if(c[i][j]>=0)
  53.         {
  54.             print(i,c[i][j]);
  55.             print(c[i][j]+1,j);
  56.         }
  57.         else{
  58.             if(ss[i]=='(')
  59.             {
  60.                 cout<<"(";
  61.                 print(i+1,j-1);
  62.                 cout<<")";
  63.             }else{
  64.                 cout<<"[";
  65.                 print(i+1,j-1);
  66.                 cout<<"]";
  67.             }
  68.         }
  69.     }
  70. }
  71. int main()
  72. {
  73.     cin>>ss;
  74.     len =ss.size();
  75.     sol();
  76.   //  cout<<d[0][len-1]<<endl;
  77.     print(0,len-1);
  78.     cout<<endl;
  79.     return 0;
  80. }

E - Little Elephant and Elections 

  1. 要在7个政党中进行选举，小象政党认为4和7是幸运数字，每个政党将被分配一个数字，若小象政党中幸运数字的个数大于其他6个政党幸运数字的个数，有多少中正确的分配方式满足条件。
  1. 首先确定第七个数的lucky值，然后分别枚举其他六个数的情况。确定了第七个数，我们就可以利用dfs深搜出每种符合条件的结果并且将结果加到ans中。
  1. #include <bits/stdc++.h>
  3. using namespace std;
  5. typedef long long ll;
  6. const int mod=1000000007;
  7. ll dp[20][20];
  8. ll res[20];
  9. int bit[20],num;
  10. ll ans;
  11. void DFS(ll now,int mx,int pt,ll cur)
  12. {
  13.     if(now>=mx)//如果其他的lucky超过小象政党的lucky值，跳出
  14.         return ;
  15.     if(pt==7)
  16.     {
  17.         if(now<mx)
  18.         {
  19.             ans+=cur;
  20.             ans%=mod;
  21.         }
  22.         return ;
  23.     }
  24.     for(int i=0;i<num;i++)
  25.     {
  26.         if(res[i])
  27.         {
  28.             res[i]--;
  29.             DFS(now+i,mx,pt+1,cur*(res[i]+1)%mod);
  30.             res[i]++;
  31.         }
  32.     }
  34. }
  35. ll dfs(ll pos,ll mx,ll limit)
  36. {
  37.     ll sum=0;
  38.     if(pos==0) return mx==0;
  39.     if(limit==0&&dp[pos][mx]!=-1)
  40.         return dp[pos][mx];
  41.     ll las=limit?bit[pos]:9;
  42.     for(int i=0;i<=las;i++)
  43.     {
  44.         sum+=dfs(pos-1,mx-(i==4||i==7),(limit==1&&bit[pos]==i));
  45.     }
  46.     if(!limit) dp[pos][mx]=sum;//位数为pos，lucky数为mx时的种类数
  47.     return sum;
  48. }
  49. void col(ll m)
  50. {
  51.     ans=num=0;
  52.     ll  y=m;
  53.     while(y)
  54.     {
  55.         bit[++num]=y%10;
  56.         y/=10;
  57.     }
  58.     for(int i=0;i<=num;i++)
  59.         res[i]=dfs(num,i,1);  //小象政党最多获得的lucky值为num，res[i]表示lucky值为i的数字的个数
  60.     res[0]-=1;
  61.     for(int i=1;i<=num;i++)
  62.         DFS(0,i,1,res[i]);   //当小象政党的lucky值为i时，其他6个政党的lucky和小于i的方案数
  63. }
  64. int main()
  65. {
  66.     ll m;
  67.     memset(dp,-1,sizeof(dp));
  68.     scanf("%lld",&m);
  69.     col(m);
  70.     printf("%lld\n",ans);
  71.     return 0;
  72. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注