程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> poj 2955 Brackets(區間DP求最長匹配子串)

poj 2955 Brackets(區間DP求最長匹配子串)

編輯:關於C++

思路:假設要求區間[i,j]的最長匹配字串,它必然可以從[i,j-1]轉移而來,有可能是s[j]與s[i]發生“關系”(匹配或不匹配),一直到s[j-1],若不發生“關系”,即s[j]跟自己發生“關系”,用for循環枚舉所有的可能,取最大值。

代碼:

 

#include
#include
#include
using namespace std;

char s[105];
int dp[105][105];//代表[i,j]區間的最長匹配子串

int check(int i,int j)
{
    if(s[i]=='('&&s[j]==')')
        return 1;
    if(s[i]=='['&&s[j]==']')
        return 1;
    return 0;
}

int main()
{
    while(scanf("%s",s)&&strcmp(s,"end")!=0)
    {
        memset(dp,0,sizeof(dp));
        int len=strlen(s);
        for(int i=0;i

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved