uva--531Compromise+dp

uva--531Compromise+dp

其實就是一個最長公共子序列的問題，不過要打印路徑。對於路徑打印,可以采取0-1背包問題的方法，第一可以利用一個二維數組記錄每個狀態的指向最後再由最後一個狀態

回推，第二可以直接由最後一個狀態結合前面的狀態轉移進行路徑打印；下面的代碼采用了第二種方法。

代碼如下：

#include

#include
#include
using namespace std;

int main()
{
    char str1[150][33],str2[150][35],temp[50];
    int dp[150][150];
    while(scanf("%s",temp)!=EOF)
    {
        int len1=1,len2=1;
        while(1)
        {
            if(temp[0]=='#')
               break;
            strcpy(str1[len1++],temp);
            scanf("%s",temp);
        }
        scanf("%s",temp);
        while(1)
        {
            if(temp[0]=='#')
                break;
            strcpy(str2[len2++],temp);
            scanf("%s",temp);
        }
        memset(dp,0,sizeof(dp));
        for(int i=1;idp[i][j-1])
                    i=i-1;
                else
                    j=j-1;
            }
            if(i==0||j==0)
                break;
        }
        for(i=k-1;i>=1;i--)
            printf("%s ",ans[i]);
        printf("%s\n",ans[0]);
    }
 return 0;
}