ZOJ 2624 Popo's Lamps（DP 记忆化搜索）

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2624

题目大意：popo要将给定数量的灯变成自己想要的颜色，有一种魔法开关，可以将一连串的灯同时变成同一个颜色。给定灯的数量和popo想要实现的状态，求最小步数

Sample Input

5

RGBGR

4

RGRG

7

ABACADA

0

Sample Output

分析：令f[x][y]表示从第 x 个灯到第 y 个灯变成目标状态的最小花费，则初始时为最大值。而f[x][x]=1。

　　则f[x][y] =min{ f[x][k-1]+f[k][y] | x<k<y}

　　当第x,y个灯的目标状态是同一颜色时，就可以一次性将2个灯变成想要的状态

代码如下：

 # include<iostream>

 # include<cstdio>

 # include<cstring>

 #define MAX 0xFFFFFF

 using namespace std;

 char str[];

 int f[][],n;

 int dfs(int x,int y)

 {

     int i;

     int min=y-x+,temp;

     for(i=x+; i<=y; i++)

     {

         if(f[x][i-]==MAX)

             f[x][i-]=dfs(x,i-);

         if(f[i][y]==MAX)

             f[i][y]=dfs(i,y);

         if(min>f[x][i-]+f[i][y])

             min=f[x][i-]+f[i][y];

     }

     if(str[x]==str[y])

     {

         if(x+<n)

         {

             if(f[x+][y]==MAX)

                 temp=dfs(x+,y);

             else

                 temp=f[x+][y];

         }

         else

             temp=;

         if(min>temp)

             min=temp;

         if(y->)

         {

             if(f[x][y-]==MAX)

                 temp=dfs(x,y-);

             else

                 temp=f[x][y-];

         }

         else

             temp=;

         if(min>temp)

             min=temp;

         if(x+<n && y->)

         {

             if(f[x+][y-]==MAX)

                 temp=dfs(x+,y-)+;    //额外增加一步将x,y2个灯变成目标状态的步骤

             else

                 temp=f[x+][y-]+;

         }

         else

             temp=;

         if(min>temp)

             min=temp;

     }

     f[x][y]=min;

     return f[x][y];

 }

 int main ()

 {

     int i,j;

     while(scanf("%d",&n) && n)

     {

         scanf("%s",str);

         for(i=; i<n; i++)

             for(j=i+; j<n; j++)

             {

                 f[i][j]=MAX;

                 f[j][i]=;

             }

         for(i=; i<n; i++)

             f[i][i]=;

         printf("%d\n",dfs(,n-));

     }

     return ;

 }

OJ返回”Non-zero Exit Code“这种错误，是因为最后没有写return 0;或者写成了return 1;之类的，只要改成return 0;就可以了

巴特西

ZOJ 2624 Popo's Lamps（DP 记忆化搜索）

最新文章

热门文章