首页 > ACM题库 > HDU-杭电 > HDU 4138-Cipher-动态规划-[解题报告]HOJ
2015
04-16

HDU 4138-Cipher-动态规划-[解题报告]HOJ

Cipher

问题描述 :

A spy is using a clever cipher technique to encode and decode messages.
The technique is very efficient as it enables him to send and receive any message, no matter how long it is with only three numbers!
After many great efforts, The Department of National Security managed to figure out how the technique works:
1. First of all, the only characters used are the space and lower case English letters. Each character is assigned an integer called the character volume, a space character has volume 1, ‘a’ has volume 2, ‘b’ has volume 3 and so on until ‘z’ which has volume 27. The volume of the whole message V is the sum of volumes of characters in the message.
2. A message consists of a number of words W, a word is a consecutive sequence of lower case letters, messages have no leading or trailing spaces and there is only one space between consecutive words.
3. For a certain V and W, let S be the lexicographically sorted set of messages that have volume V and consists of exactly W words. We can refer to a certain message using its one-based index I in S.
So when the spy wants to send a message M, he calculates its Volume V and the number of words it contains W and finds its index I in the corresponding set S (its index among all sorted messages of volume V with W words) and sends only three numbers along: V, W and I!
The Department of National Security has done a great effort so far, yet they seek your help to decode messages sent by the spy! That is, given V, W and I you must decrypt the spy’s message or determine that there is no such one!

输入:

The first line of input contains an integer (1 <= T <= 200), the number of test cases.
Each data set consists of a line with three integers the volume of the message (1 <= V <= 75), the number of words (1 <= W <= 20), and the index of message (1 <= I <= 1018).

输出:

The first line of input contains an integer (1 <= T <= 200), the number of test cases.
Each data set consists of a line with three integers the volume of the message (1 <= V <= 75), the number of words (1 <= W <= 20), and the index of message (1 <= I <= 1018).

样例输入:

3
7 2 3
2 1 2
50 2 39098532022

样例输出:

Case #1: aa a
Case #2: Corrupted!
Case #3: big bang

Hint
In the first test case, the sorted set of messages of volume 7 which contain 2 words is {“a aa”, “a c”, “aa a”, “b b”, “c a”}, hence the third and required message is “aa a”. In the second test case, the sorted set of messages of volume 2 which contain 1 word is {“a”}, the set has only one message while index 2 is required, so something must have gone wrong!

比赛时候推出了dp,但时间不够了,没敲出来,结束后理了下思路,并不算很难

平常做按位dp,比如说求某一个范围内满足某个要求的数字串第几个是多少,dp[i][j] 表示位数为i时以j开头的串多少个,这题就算一个加强版,求价值为V的第I个串,就可以用一个dp[i][j]表示价值为i时第一个字符为j的串的个数,他还有一个空格的限制,于是dp外加一维dp[i][j][k]用k表示空格数,方程推起来也简单,注意好不能连续空格就行了,然后从前往后去确定对应位置的字符

标程用的是dp[75][20][2]的方法,不太清楚是怎么做的,第三维表示首位是否为空格????

 #include<cstdio>
 #include<cstring>
 using namespace std;
 
 
 __int64 dp[100][30][30];
 
 int ans[100];
 int main(){
     memset(dp,0,sizeof(dp));
     dp[0][1][0]=1;
     for(int i=2;i<=75;i++){
         for(int j=1;j<=27;j++){
             for(int k=0;k<=20;k++){
                 __int64 val=0;
                 if(j==1){
                     if(k==0) continue;
                     for(int jj=2;jj<=27;jj++){
                         if(i>=j) val+=dp[i-j][jj][k-1];
                     }
                 }else{
                     for(int jj=1;jj<=27;jj++){
                         if(i>=j) val+=dp[i-j][jj][k];
                     }
                 }
                 dp[i][j][k]=val;
             }
         }
     }
     
     int t,cas=0;
     scanf("%d",&t);
     while(t--){
         int V,W;
         __int64 I;
         scanf("%d%d%I64d",&V,&W,&I);
         printf("Case #%d: ",++cas);
         W-=1;
         I-=1;
         ans[0]=-1;
         for(int i=2;i<=27;i++){
 //            printf("%d %d %d %I64d: %I64d\n",V,i,W,I,dp[V][i][W]);
             if(I>=dp[V][i][W]){
                 I-=dp[V][i][W];
             }else{
                 V-=i;
                 ans[0]=i;
                 break;
             }
         }
         if(ans[0]==-1){
             puts("Corrupted!");
             continue;
         }
         int cnt=1;
         bool flag=false;
         while(true){
             for(int i=1;i<=27;i++){
                 if(flag&&(i==1)) continue;
                 if((W==0)&&(i==1)) continue;
                 flag=false;
 //                printf("%d %d %d %I64d: %I64d\n",V,i,W,I,dp[V][i][W]);
                 if(I>=dp[V][i][W]){
                     I-=dp[V][i][W];
                 }else{
                     V-=i;
                     if(i==1){W-=1;flag=true;}
                     ans[cnt++]=i;
                     break;
                 }
             }
             if(V==0) break;
         }
         for(int i=0;i<cnt;i++){
             if(ans[i]==1) putchar(' ');
             else putchar(ans[i]-2+'a');
         }
         puts("");
     }
 }

参考:http://www.cnblogs.com/ambition/archive/2011/12/12/Cipher.html


  1. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯