紫书动规例题9-7 UVA

题目链接:

题意:

题解:

dp[i]:=考虑到第i个字符，的最少划分
dp[i] = min{dp[j]+1} (0<=j）

代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 1e3+10;
17 
18 int n,kase,vis[maxn][maxn],p[maxn][maxn],dp[maxn];
19 char s[maxn];
20 
21 int is_palindrome(int i,int j){
22     if(i>j) return 1;
23     if(s[i] != s[j]) return 0;
24 
25     if(vis[i][j] == kase) return p[i][j];
26     vis[i][j] = kase;
27     p[i][j] = is_palindrome(i+1,j-1);
28     return p[i][j];
29 }
30 
31 int main(){
32     int T = read();
33     for(kase=1; kase<=T; kase++){
34         scanf("%s",s+1);
35         // dp[i] = min(dp[i],dp[j]+1); is_palindrome(j+1,i);
36         int len = strlen(s+1);
37         // memset(dp,0x3f,sizeof(dp));
38         dp[0] = 0;
39         for(int i=1; i<=len; i++){
40             dp[i] = dp[i-1]+1;
41             for(int j=0; j<i; j++){
42                 if(is_palindrome(j+1,i))
43                     dp[i] = min(dp[i],dp[j]+1);
44                 // cout << i << " " << dp[i] << " 
";
45             }
46         }
47 
48         cout << dp[len] << endl;
49     }
50 
51     return 0;
52 }
53 
54 // 3
55 // racecar
56 // fastcar
57 // aaadbccb

紫书动规 例题9-7 UVA

题目链接:

题意:

题解:

代码:

紫书动规例题9-7 UVA