ÅÚ±øÕóµØ
| Time Limit: 2000MS |
|
Memory Limit: 65536K |
| Total Submissions: 19690 |
|
Accepted: 7602 |
Description
˾ÁµÄ½«¾üÃÇ´òËãÔÚN*MµÄÍø¸ñµØÍ¼Éϲ¿ÊðËûÃǵÄÅÚ±ø²¿¶Ó¡£Ò»¸öN*MµÄµØÍ¼ÓÉNÐÐMÁÐ×é³É£¬µØÍ¼µÄÿһ¸ñ¿ÉÄÜÊÇɽµØ£¨ÓÃ"H" ±íʾ£©£¬Ò²¿ÉÄÜÊÇÆ½Ô£¨ÓÃ"P"±íʾ£©£¬ÈçÏÂͼ¡£ÔÚÿһ¸ñƽԵØÐÎÉÏ×î¶à¿ÉÒÔ²¼ÖÃÒ»Ö§ÅÚ±ø²¿¶Ó£¨É½µØÉϲ»Äܹ»²¿ÊðÅÚ±ø²¿¶Ó£©£»Ò»Ö§ÅÚ±ø²¿¶ÓÔÚµØÍ¼ÉϵĹ¥»÷·¶Î§ÈçͼÖкÚÉ«ÇøÓòËùʾ£º
Èç¹ûÔÚµØÍ¼ÖеĻÒÉ«Ëù±êʶµÄƽÔÉϲ¿ÊðÒ»Ö§ÅÚ±ø²¿¶Ó£¬ÔòͼÖеĺÚÉ«µÄÍø¸ñ±íʾËüÄܹ»¹¥»÷µ½µÄÇøÓò£ºÑغáÏò×óÓÒ¸÷Á½¸ñ£¬ÑØ×ÝÏòÉÏϸ÷Á½¸ñ¡£Í¼ÉÏÆäËü°×É«Íø¸ñ¾ù¹¥»÷²»µ½¡£´ÓͼÉϿɼûÅÚ±øµÄ¹¥»÷·¶Î§²»ÊܵØÐεÄÓ°Ïì¡£
ÏÖÔÚ£¬½«¾üÃǹ滮ÈçºÎ²¿ÊðÅÚ±ø²¿¶Ó£¬ÔÚ·ÀÖ¹ÎóÉ˵ÄǰÌáÏ£¨±£Ö¤ÈκÎÁ½Ö§ÅÚ±ø²¿¶ÓÖ®¼ä²»ÄÜ»¥Ï๥»÷£¬¼´ÈκÎÒ»Ö§ÅÚ±ø²¿¶Ó¶¼²»ÔÚÆäËûÖ§ÅÚ±ø²¿¶ÓµÄ¹¥»÷·¶Î§ÄÚ£©£¬ÔÚÕû¸öµØÍ¼ÇøÓòÄÚ×î¶àÄܹ»°Ú·Å¶àÉÙÎÒ¾üµÄÅÚ±ø²¿¶Ó¡£
Input
µÚÒ»Ðаüº¬Á½¸öÓɿոñ·Ö¸î¿ªµÄÕýÕûÊý£¬·Ö±ð±íʾNºÍM£»
½ÓÏÂÀ´µÄNÐУ¬Ã¿Ò»Ðк¬ÓÐÁ¬ÐøµÄM¸ö×Ö·û('P'»òÕß'H')£¬ÖмäûÓпոñ¡£°´Ë³Ðò±íʾµØÍ¼ÖÐÿһÐеÄÊý¾Ý¡£N <= 100£»M <= 10¡£
Output
½öÒ»ÐУ¬°üº¬Ò»¸öÕûÊýK£¬±íʾ×î¶àÄܰڷŵÄÅÚ±ø²¿¶ÓµÄÊýÁ¿¡£
Sample Input
5 4
PHPP
PPHH
PPPP
PHPP
PHHP
Sample Output
6
²»ÈÝÒ×°¡£¬debugÁËÒ»ÏÂÎç¡£¡£¡£
#include
#include
#include
#include
#include
#include
using namespace std; #define N 150 const int inf=0x7fffffff; int map[N]; char g[N][15]; int top,num[N],cnt[N]; int dp[N][65][65]; int getnum(int x) //µÃµ½Ò»ÖÖ°Ú·Å·½Ê½´óÅڵĸöÊý { int t=0; while(x) { if(x&1) t++; x>>=1; } return t; } void inti(int m) { int i; top=0; for(i=0;i<(1<