终于搞定经典DP - ZOJ 1022 / HDOJ 1367 (Parallel Expectations)

极光炫影 发表于 2006-12-08 21:57:21

/*
 
Solution for ZOJ 1022 / HDOJ 1367 - Parallel Expectations
Author: JGShining
Date: 2006/12/08

NOTE:

今天看概率的时候，
突然想起来自己这个一直没有过的ZOJ1022，
于是重新写了全部代码，
仔细分析和编码以后终于让我AC了。
这个题目是非常经典的DP题目，
看来概率还是很好的东西。^_^
事后想想其实以前版本的代码只是错了一个很小的地方......

当然，《算法艺术与信息学竞赛》（黑书）上关于这个题目的分析是错误的，
因为lrj将这个题目分析为了每种结果等概率，
其实是不等概率的，
这样，期望值就不等于平均值。

我自己感觉这个代码是相当快而且占用内存很小的，
里面尽量避免了很花时间的浮点除法。
当然，优化的余地还是有很多的，
不过懒得优化了。
目前这个代码跑出了ZOJ、HDOJ和POJ上最好的成绩（POJ 第一的那个我肯定是直接输出答案的）。
 
和我的别的经典问题的solution一样，
这个代码被我人为隐藏了部分，
有兴趣的补全吧^_^
 
*/
 
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
#define MOV   0
#define ADD   4
#define SUB   5
 
static char* delimiter = " \t:=+-";
static char* terminator = "END";
 
struct token_list_node
{
     char name[21];
     int id;
     token_list_node* next;
};
 
struct ins_list_node
{
     int operand_id;
     int operator_id;
};
 
token_list_node token_list_header;
ins_list_node ins_stream[2][101];
int token_list_size, ins_count[2];
char line_buffer[256];
double value[101][101][14];
double probability[101][101];
int cas;
 
// if the specified token has already existed in the token list,
//    just return the id of the token which identified the token uniquely.
// if not, insert a new node to the ascendingly sorted token list and return its
//    id.
 
int find_token(char* token)
{
     token_list_node *last, *node, *temp;
     int cmp_result = -1;
    
     last = &token_list_header;
     node = token_list_header.next;
 
     while(node)
     {
         cmp_result = strcmp(node->name, token);
         if(cmp_result == 0)
              return node->id;
         else if(cmp_result > 0)
              break;
         last = node;
         node = node->next;
     }
 
     temp = (token_list_node*)malloc(sizeof(token_list_node));
     strcpy(temp->name, token);
     temp->next = node;
     temp->id = token_list_size++;
     last->next = temp;
 
     return temp->id;
}
 
// free the token list
 
void destroy_token_list()
{
     token_list_node* temp;
     while(token_list_header.next)
     {
         temp = token_list_header.next;
         token_list_header.next = temp->next;
         free(temp);
     }
     token_list_size = 0;
}
 
// get the next token from the given line
// return values:
//   = 0 -- a token terminated by 0 has been copied to the region pointed by buffer
//   > 0 -- return value is a constant
 
int next_token(char* line, char* buffer)
{
     int value = 0;
     char* token = strtok(line, delimiter);
     if(token != NULL)
     {
         if(*token >= '0' && *token <= '9')
         {
              while(*token)
                   value = value * 10 + *(token++) - '0';
              return value;
         }
         else
         {
              do
              {
                   if(*token >= 'A' && *token <= 'Z')
                       *(buffer++) = *(token++) - 'A' + 'a';
                   else
                       *(buffer++) = *(token++);
              }
              while(*token);
              *buffer = 0;
         }
     }
     return 0;
}
 
// get the operator type of either '+' or '-' of a line
// zero will be returned if not found.
 
int get_operator(char* line)
{
     while(*line && *line != '+' && *line != '-')
         line++;
     if(*line == '+')
         return ADD;
     else if(*line == '-')
         return SUB;
     else
         return 0;
}
 
// parse a line and store the result into instruction streams
 
int parse_line(char* line, int start_index, int program_id)
{
     static int i, token_index[4];
     static char token_name[21];
 
     ins_stream[program_id][start_index + 2].operator_id = get_operator(line);
     next_token(line, token_name);
     token_index[0] = find_token(token_name);
     ins_stream[program_id][start_index].operator_id = 0;
    
     for(i = 1; i < 4; ++i)
     {
         if(token_index[i] = next_token(NULL, token_name))
              token_index[i] += 100; // the constant itself will increase by 100, then the value is used as its 'id'
         else
              token_index[i] = find_token(token_name);
 
         if(i != 2)
              ins_stream[program_id][start_index + i].operator_id = i;
     }
 
     ins_stream[program_id][start_index + 0].operand_id = token_index[1];
     ins_stream[program_id][start_index + 1].operand_id = token_index[2];
     ins_stream[program_id][start_index + 3].operand_id = token_index[0];
 
     return start_index + 4;
}
 
// execute an instruction and store the result in dest_var_list
 
void execute_ins(int program_id, ins_list_node* ins, double* dest_var_list, double* orig_var_list)
{
     // THIS PART HAS BEEN HIDDEN !!!
}
 
// solve the problem with DP method
 
void dynamic_programming()
{
     int i, j, k;
     double var_list[2][14], p1;
    
     // compute the probabilities
     probability[0][0] = 1.0;
     for(i = 1; i <= ins_count[0]; ++i)
         probability[i][0] = probability[i - 1][0] * 0.5;
     for(j = 1; j <= ins_count[1]; ++j)
         probability[0][j] = probability[0][j - 1] * 0.5;
     for(i = 1; i <= ins_count[0]; ++i)
     {
         for(j = 1; j <= ins_count[1]; ++j)
         {
              if(i == ins_count[0])
                   probability[i][j] = probability[i - 1][j] * 0.5 + probability[i][j - 1];
              else if(j == ins_count[1])
                   probability[i][j] = probability[i - 1][j] + probability[i][j - 1] * 0.5;
              else
                   probability[i][j] = (probability[i - 1][j] + probability[i][j - 1]) * 0.5;
         }
     }
     probability[ins_count[0]][ins_count[1]] = 1.0;
 
     // compute variable values
     memset(value[0][0], 0, sizeof(double) * 14);
     for(i = 1; i <= ins_count[0]; ++i)
         execute_ins(0, &ins_stream[0][i], value[i][0], value[i - 1][0]);
     for(j = 1; j <= ins_count[1]; ++j)
         execute_ins(1, &ins_stream[1][j], value[0][j], value[0][j - 1]);
     for(i = 1; i <= ins_count[0]; ++i)
     {
         for(j = 1; j <= ins_count[1]; ++j)
         {
              execute_ins(0, &ins_stream[0][i], var_list[0], value[i - 1][j]);
              execute_ins(1, &ins_stream[1][j], var_list[1], value[i][j - 1]);
             
              if(i == ins_count[0])
                   p1 = probability[i][j - 1] / probability[i][j];
              else
                   p1 = probability[i][j - 1] * 0.5 / probability[i][j];
 
              for(k = 0; k < token_list_size; ++k)
                   value[i][j][k] = var_list[0][k] * (1.0 - p1) + var_list[1][k] * p1;
             
              value[i][j][10] = var_list[0][10] * (1.0 - p1) + var_list[1][10] * p1;
              value[i][j][11] = var_list[0][11] * (1.0 - p1) + var_list[1][11] * p1;
              value[i][j][12] = var_list[0][12] * (1.0 - p1) + var_list[1][12] * p1;
              value[i][j][13] = var_list[0][13] * (1.0 - p1) + var_list[1][13] * p1;
         }
     }
}
 
// output our result
 
void output_result()
{
     int i, j, k;
     token_list_node* node = token_list_header.next;
 
     for(; node;)
     {
         printf("%.4lf\n", value[ins_count[0]][ins_count[1]][node->id]);
         node = node->next;
     }
 
     if(cas > 0)
         printf("\n");
}
 
int main()
{
     scanf("%d", &cas);
     while(cas--)
     {
         // absurb the blank line
         gets(line_buffer);
        
         // parse the first program
         ins_count[0] = 1;
         while(gets(line_buffer) && strcmp(line_buffer, terminator))
              ins_count[0] = parse_line(line_buffer, ins_count[0], 0);
 
         // parse the second program
         ins_count[1] = 1;
         while(gets(line_buffer) && strcmp(line_buffer, terminator))
              ins_count[1] = parse_line(line_buffer, ins_count[1], 1);
 
         ins_count[0]--;
         ins_count[1]--;
 
         // solve the problem with DP method
         dynamic_programming();
 
         // output the result
         output_result();
 
         // free the token list
         destroy_token_list();
     }
     return 0;
}
阅读1788次 评论7条 个人主页 扔小纸条 文件夹: 算法设计
收藏: QQ书签 del.icio.us

最新评论


  • 行云流水
    2006-12-10 12:49:55

    阿  晕阿

  • Box
    2009-03-20 14:43:05 匿名 203.156.*.*

    虽然你的程序通过了测试，但我还想给你提几条建议。
    (1)程序不够健壮。当输入中有某个运算数是0时，你的程序就错出了，如下面的组输入。不应该期待测试数据中没有这种情况。
    1
    q:=s+8
    END
    s:=q+3
    s:=s+0
    END
    (2)你有没有想过。
    MOV R2 opd
    ADD R1 R2
    其实可以写成：
    ADD R1 opd
    NOP——因为要算概率，加空语句
    这样就可以各节省一个寄存器和不必要的移动。
    (3)一些细节问题。

  • 极光炫影
    2009-03-25 15:04:10 匿名 60.12.*.*

    谢谢你的分析，但是有些话还是要说：
    1、这个程序是不完整的，因为我省略了相当重要的部分代码，所以不可能预期产生正确的结果的，那么你说的(1)是不是有待商榷呢。我根本就没有考虑操作数是不是0的问题，因为那很显然：0是合法的
    2、暂且不说你这样的做法是否正确，你觉得你这样做有必要么？题目中没有提出NOP指令的问题，你干嘛给自己出麻烦处理无操作数指令的呢？你认为做这个程序的效率会更好么？这个题目的关键是减少DP的时间而不是这种无聊的处理，更何况这样的处理不仅给自己增加麻烦而且还要加特殊判断从而降低效率！

    PS：这个程序可以优化，但是不是你说的那些，而是比如采用滚动数组之类的来降低内存占用。最后，请注意这个仅仅是ACM比赛的程序，不要用你的那种有点不是很高明的软件工程的观点来考虑问题，谢谢！

  • Box
    2009-04-01 23:05:36 匿名 58.24.*.*

    呼呼，恐怕你低估我的认真程度了。我是认真研究完你的程序并补完了你空缺的部分，再测试，再验证的。好吧，我讲的再详细一点。
    函数next_token返回value或者0。0表示变量，value表示直接数。那么，当直接数等于0时不就出错了吗。修改很简单。返回－1或者value。同时修改函数parse_line中的相应语句即可。庆幸的是，测试里没有操作数0。

  • Box
    2009-04-01 23:37:53 匿名 58.24.*.*

    下面再讲第二个问题(看来你没有理解我的意思)。
    以加法为例，题目中认为每个语句需要编译成四句：
    Mov R1, Y;  Mov R2, Z;  Add R1, R2;   Mov X, R1 ;
    通过分析发现，Z移入R2后，另一个进程对Z的改变已经不影响本进程计算X了，故实际可以编译成：
    Mov R1, Y;  Add R1, Z;  NOP;   Mov X, R1 ;
    添加NOP语句仅仅是为了计算概率需要。这样不就把一步移入R2的操作替换成空操作了吗？这步修改不仅通过本地测试，而且确实是AC的。
    你可以再仔细研究一下，这步修改提高的时间效率在1/4不到，空间效率在1/12左右。

  • Box
    2009-04-01 23:59:36 匿名 58.24.*.*

    最后讲一个dp过程中，double var_list[2][14]其实是可以通过数据的原地操作节省下来的。大致上是：
    value[i-1][j]  i操作后存入 value[i][j]
    value[i][j-1]  j操作后存入 value[i][j-1]
    value[i][j] 合并 vlue[i][j-1]
    你说的滚动数组我当初自己做的时候也想过，但写着写着就被繁得放弃了（惭愧）。
    不过，我确实不是软工的（好像很软工很丢人似的，汗），只是碰巧发现了你的程序，然后研究一下，既然吸收过别人长处了，总也要帮助别人也提高一下。鉴于每篇帖子的长度，于是写下了最早的那一篇，没想到产生了误会。歉意，歉意。

  • Box
    2009-04-02 00:33:53 匿名 58.24.*.*

    啊呀，写错了。第二步改进在空间上的提高应该是2/14，不是1/12。
    顺便说一下，时间上的提高指的是在函数execute_ins里，内存拷贝提高了1/7（内存使用再合理些可能更高些），其他运算提高了1/4。当然从总体上看，确实很有限。
    你还问了个为什么要有NOP？那完全是为了计算概率需要，所以不能简单把4步汇编改成3步。具体的要自己理解了。

发表评论

*昵称

已经注册过? 请登录
Email
网址
*评论