¡¡¡¡AÁËÒ»ÕûÌì~~~ÖÕÓÚ¸ãµôÁË¡£
¡¡¡¡ÕæÊÇѪ¶¼A³öÀ´ÁË¡£
¡¡¡¡ÌâÄ¿Òâ˼ºÜÇå³þ£¬¿Ï¶¨ÊÇ״ѹDP¡£
¡¡¡¡ÎÒÃÇ¿ÉÒÔÁªÏµÒ»ÏÂPOJ 1185 ÅÚ±øÕ󵨣¬¾µäµÄ״ѹDP¡£
¡¡¡¡Á½µÀÌâµÄÇø±ð¾ÍÔÚÓÚ£¬ÕâµÀÌâµÄ¹¥»÷ÊÇ¿ÉÒÔ±»Xµ²×¡µÄ£¬¶øÇÒ¹¥»÷µÄ·¶Î§²»Í¬¡£

¡¡¡¡ÕâÊÇÕâµÀÌâµÄ¹¥»÷·¶Î§¡£
¡¡¡¡µ«ÊÇÕâ¸ö¹¥»÷·¶Î§ÊǻᱻXµ²×¡µÄ¡£
¡¡¡¡ËùÒÔµÃÔÚ1185ÉϼÓÒԸĽø¡£
¡¡¡¡·ÖÎö£º
¡¡¡¡POJ 1185£¬ÒòΪ¿ÉÒÔ¸ô×ÅÕϰÎï´ò£¬ËùÒÔËûÿÐеÄ״̬ÊÇÒ»ÑùµÄ£¬µ«ÊÇÕâÌâÓÉÓÚ¹¥»÷»á±»µ²×¡£¬ËùÒÔÿÐеÄ״̬ÊDz»Ò»ÑùµÄ£¬ËùÒÔÎÒÃÇÔ¤´¦ÀíµÄʱºò¾ÍÒª´¦Àí³öÿһÐеÄ״̬Êý£¬·Ö±ð±£´æ£¬È»ºó´æÏÂÿÐÐÿ¸ö״̬µÄÊýÁ¿¡£
¡¡¡¡ÒòΪÎÒµÄϱêÊÇ´Ó0¿ªÊ¼µÄ£¬ËùÒÔÎÒµÃÔ¤ÏÈ´¦ÀíһϵÚ0Ðк͵Ú1ÐеÄ×´Ì¬×ªÒÆ¹ý³Ì£¬Õâ¸öºÜºÃ´¦Àí£¬¾ßÌå¿´´úÂë¡£
¡¡¡¡ÄÇôԤ´¦ÀíÍê±ÏÖ®ºó¾ÍÊÇ×´Ì¬×ªÒÆµÄ¹ý³Ì¡£
¡¡¡¡±äÁ¿¶¨Ò壺
¡¡¡¡M[i] £ºÃ¿Ò»ÐеĵØÍ¼Ñ¹Ëõ¡£
¡¡¡¡st[i][j] £ºµÚjÐУ¬µÚi¸ö״̬¡£
¡¡¡¡Count[i][j] £ºµÚjÐеÚi¸ö״̬µÄÊýÁ¿¡£
¡¡¡¡num[i]£ºµÚi ÐÐ״̬µÄ×ÜÊý¡£
¡¡¡¡dp[i][j][k] £ºµÚiÐеÄ״̬ÊÇk ,µÚi - 1 ÐеÄ״̬ÊÇjµÄ¿ÉÐÐ״̬×ÜÊý¡£
¡¡¡¡ÕâµÀÌâÃ²ËÆ»¹¿¨Äڴ棬±ØÐëʹÓùö¶¯Êý×飬ÒòΪ״ѹµÄʱºòËûÖ»ÐèÒª3¸ö״̬£¬ËùÒÔÕâÀïi¿ªµ½3¾Í¿ÉÒÔÁË¡£
¡¡¡¡×´Ì¬×ªÒƵĹý³Ì£¬Ê×Ïȵ±Ç°×´Ì¬ÊÇk ,ÉÏһ״̬ÊÇj£¬ÉÏÉÏ״̬ÊÇl ¡£
¡¡¡¡ÄÇôÊ×ÏÈÅжÏk ºÍ jµÄ״̬¿ÉÐÐÐÔ£¬Ê×ÏÈj²»ÄܳöÏÖÔÚkµÄÉÏ·½£¬ÄǾÍÊÇ(st[j][i - 1] & st[k][i]) £¬È»ºók Ò²²»ÄܳöÏÖÔÚjµÄ×óϺÍÓÒϵÄλÖã¬Í¨¹ýÉÏͼ¿ÉÒÔ¿´³ö£¬k²»ÄܳöÏÖÔÚjµÄ×óÒÆÒ»Î»£¬ÓÒÒÆÒ»Î»µÄλÖá£ÄÇô¿ÉÒÔÕâôÅжÏ(st[j][i - 1] >> 1 & st[k][i]), (st[j][i - 1] << 1 & st[k][i]) ¡£ÕâÑù¾Í´¦ÀíÍêj ºÍk ÕâÁ½¸ö״̬ÁË¡£
¡¡¡¡½ÓÏÂÀ´ÊÇjºÍl£¬ÕâÀïµÄÅжÏͬjºÍk£¬ÒòΪ¶¼ÊÇÏàÁÚµÄÁ½ÐУ¬ÕâÀï²»¶à˵ÁË£¬Ò»ÑùµÄ£¬ÏÂÃæ×ÅÖØ½²Ò»ÏÂlºÍkµÄ״̬µÄÅжϡ£
¡¡¡¡ÒòΪlºÍkÖ®¼äÊÇ¿ÉÄܸô×ÅXµÄ£¬ËùÒÔÎÒÃDz»ÄÜÖ±½ÓÅжϣ¬¶øÓ¦¸ÃÅжÏËûÃÇÖ®¼äÊÇ·ñÓÐX¡£
¡¡¡¡±ÈÈçÅжÏlÊÇ·ñÔÚkÉÏ·½£¬ÄÇô²»ÄÜÖ±½Ó(st[l][i - 2] & st[k][i])£¬ÒòΪËûÃÇÖ®¼äÈç¹ûÓÐX£¬ÄÇô¸Ã״̬ÊdzÉÁ¢µÄ¡£
¡¡¡¡ÄÇôµ½µ×ÈçºÎÅжÏÄØ¡£×òÌìÎÒÒ²ÊÇÔÚÕâÀ│סÁË£¬½ñÌìÔçÉÏͻȻÏëµ½£¬ÆäʵÎÒÃÇÖ»ÒªÅжÏl״̬ºÍk״̬¶¼ÊÇ1µÄλÖã¬ÄÇôËûÃǵÄi - 1ÐиÃλÖÃÊÇ·ñÊÇX¾ÍÐÐÁË¡£¶øÅжÏXÎÒÃÇ¿ÉÒÔÖ±½ÓʹÓÃѹËõ¹ýµÄµØÍ¼½øÐÐÅжϡ£
¡¡¡¡ÄÇô¿ÉÒÔÕâÑù£º
¡¡¡¡int s = (st[l][i - 1] & st[k][i]) ;
¡¡¡¡if(s & M[i - 1] != s)
¡¡¡¡ÄÇô¾ÍÖ¤Ã÷ËûÃÇÖ®¼äÊǻụÏ๥»÷µÄ£¬s & (M[i -1] ) != s£¬¾Í˵Ã÷lºÍk¶¼Îª1µÄλÖÃËûÃÇÖмäÖÁÉÙÓÐÒ»´¦²»ÎªX£¬ÄÇô¸Ã״̬²»¿ÉÐС£
¡¡¡¡Í¬ÀíÎÒÃÇ¿ÉÒÔÅÐ¶Ï l״̬µÄ×óϹ¥»÷ºÍÓÒϹ¥»÷ÊÇ·ñ»á´òµ½k״̬¡£
¡¡¡¡Èç¹ûÊÇ×óϹ¥»÷£¬ÄÇôֻÐèÒª½«l״̬×óÒÆÁ½Î»ÓëkÅжϣ¬È»ºóÅжÏËûÃǵÄÖ®¼äÊÇ·ñÓÐX¡£¾ßÌå¿´´úÂ룬ÎҾͲ»¶à½âÊÍÁË£¬ÏàÐÅ×Ô¼º¶¯ÊÖ»ÕÅͼ»¹ÊǺܺÃÀí½âµÄ¡£
¡¡¡¡Í¬ÀíÓÒϹ¥»÷¡£