Tag:DP
Article From:https://www.cnblogs.com/HDUjackyan/p/9123199.html

 

Example: the following examples are from https://blog.csdn.net/my_sunshine26/article/details/77141398

One, the problem of the consolidation of stone

1.(NYOJ737)http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=737

Analysis: we dp[i][j] represent the minimum cost of merging I piles to j piles. Then the state transition equation is dp[i][j]=min (dp[i][k]+dp[k+1][j]+w[i][j]) s[i][j-1]&lt (= =).K< =s[i+1][j])

 In which w[i][j] represents the cost of merging the two parts, that is, from the I heap to the number of the stacks of the j heap, and in order to facilitate the query, we can use sum[i] to represent the number of stones from the first heap to the I heap, then w[i][j]=sum[j]-sum[i-1].

Using s[i][j] to represent the optimal partition point in interval [i and j], then the third loop can be optimized from [i, J-1 to [s[i][j-1], s[i+1][j]].

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 typedef long long ll;
 6 const int maxn=210;
 7 const ll inf=1e18;
 8 ll dp[maxn][maxn];
 9 ll sum[maxn],a[maxn];
10 int s[maxn][maxn];
11 
12 int main()
13 {
14     int n,i,j,k,x,y,z,len;
15     while ( scanf("%d",&n)!=EOF )
16     {
17         for ( i=1;i<=n;i++ )
18         {
19             for ( j=1;j<=n;j++ ) dp[i][j]=inf;
20             dp[i][i]=0;
21             s[i][i]=i;
22         }
23         sum[0]=0;
24         for ( i=1;i<=n;i++ ) 
25         {
26             scanf("%lld",&a[i]);
27             sum[i]=a[i]+sum[i-1];
28         }
29         for ( len=2;len<=n;len++ )
30         {
31             for ( i=1;i<=n;i++ )
32             {
33                 j=len+i-1;
34                 if ( j>n ) break;
35                 for ( k=s[i][j-1];k<=s[i+1][j];k++ ) 
36                 {
37                     if ( dp[i][j]>dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1] )
38                     {
39                         dp[i][j]=dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];
40                         s[i][j]=k;
41                     }
42                 }
43             }
44         }
45         printf("%lld\n",dp[1][n]);
46     }
47     return 0;
48 } 

NYOJ737

 

2.(HDOJ3506)http://acm.hdu.edu.cn/showproblem.php?pid=3506

The upgraded version of the last question turns the upper level into a circle. At this point, we only need to turn N into n=2*N-1, and finally ans=min (dp[i][i+n-1]).

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 typedef long long ll;
 6 const int maxn=2010;
 7 const ll inf=1e18;
 8 ll dp[maxn][maxn];
 9 ll sum[maxn],a[maxn];
10 int s[maxn][maxn];
11 
12 int main()
13 {
14     int n,i,j,k,x,y,z,len,N;
15     ll ans;
16     while ( scanf("%d",&N)!=EOF )
17     {
18         n=2*N-1;
19         for ( i=1;i<=n;i++ )
20         {
21             for ( j=1;j<=n;j++ ) dp[i][j]=inf;
22             dp[i][i]=0;
23             s[i][i]=i;
24         }
25         sum[0]=0;
26         for ( i=1;i<=N;i++ ) 
27         {
28             scanf("%lld",&a[i]);
29             sum[i]=a[i]+sum[i-1];
30         }
31         for ( i=1;i<N;i++ ) sum[i+N]=a[i]+sum[i+N-1];
32         for ( len=2;len<=N;len++ )
33         {
34             for ( i=1;i<=n;i++ )
35             {
36                 j=len+i-1;
37                 if ( j>n ) break;
38                 for ( k=s[i][j-1];k<=s[i+1][j];k++ )
39                 {
40                     if ( dp[i][j]>dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1] )
41                     {
42                         dp[i][j]=dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];
43                         s[i][j]=k;
44                     }
45                 }
46             }
47         }
48         ans=inf;
49         for ( i=1;i<=N;i++ )
50         {
51             j=i+N-1;
52             ans=min(ans,dp[i][j]);
53         }
54         printf("%lld\n",ans);
55     }
56     return 0;
57 } 

HDOJ3506

 

Two, the problem of parenthesis matching

1.(POJ2955)http://poj.org/problem?id=2955

Topic: give a string consisting of four brackets of ‘(””””””””””””””””””””””””””””””””””””””””””””””””””””””””””””””” ”

Analysis: use dp[i][j] to represent the largest complete match number in interval [i and j]. As long as you get dp[i][j], you can get dp[i-1][j+1] dp[i-1][j+1]=dp[i][j]+ (s[i-1] in s[j+1).] match? 2:0).

Then we use the state transition equation to update the interval optimal solution. Dp[i][j]=max (dp[i][j], dp[i][k]+dp[k+1][j])

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 typedef long long ll;
 6 const int maxn=105;
 7 char s[maxn];
 8 ll dp[maxn][maxn];
 9 
10 int main()
11 {
12     int n,i,j,k,x,y,z,len;
13     while ( scanf("%s",s+1)!=EOF && s[1]!='e' )
14     {
15         n=strlen(s+1);
16         memset(dp,0,sizeof(dp));
17         for ( len=2;len<=n;len++ )
18         {
19             for ( i=1;i<=n;i++ )
20             {
21                 j=i+len-1;
22                 if ( j>n ) break;
23                 if ( (s[i]=='('&&s[j]==')') || (s[i]=='['&&s[j]==']') ) dp[i][j]=dp[i+1][j-1]+2;
24                 for ( k=i;k<j;k++ ) dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);
25             }
26         }
27         printf("%lld\n",dp[1][n]);
28     }
29     return 0;    
30 } 

POJ2955

 

2.(NYOJ15)http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=15

Analysis: at least the number of brackets added = the total brackets maximum number of brackets, the code is basically the same on the last question.

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 typedef long long ll;
 6 const int maxn=105;
 7 char s[maxn];
 8 ll dp[maxn][maxn];
 9 
10 int main()
11 {
12     int n,i,j,k,x,y,z,len,T;
13     scanf("%d",&T);
14     while ( T-- )
15     {
16         scanf("%s",s+1);
17         n=strlen(s+1);
18         memset(dp,0,sizeof(dp));
19         for ( len=2;len<=n;len++ )
20         {
21             for ( i=1;i<=n;i++ )
22             {
23                 j=i+len-1;
24                 if ( j>n ) break;
25                 if ( (s[i]=='('&&s[j]==')') || (s[i]=='['&&s[j]==']') ) dp[i][j]=dp[i+1][j-1]+2;
26                 for ( k=i;k<j;k++ ) dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);
27             }
28         }
29         printf("%lld\n",n-dp[1][n]);
30     }
31     return 0;    
32 } 

NYOJ15

 

Three, integer division problem

1.(NYOJ746)http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=746

Analysis: use dp[i][j] to indicate the maximum value of product after inserting J multipliers from first to I bits. According to the idea of interval DP, we can calculate the result of inserting multiple multipliers from the result of inserting fewer multipliers.

 The method is to enumerate the placement when we want to put the multipliers of J. The state transition equation is dp[i][j]=max (dp[i][j], dp[k][j-1]*num[k+1][i]). In which num[i][j] represents the link from s[i] to s[j]The value of the continued interval representation.

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 typedef long long ll;
 6 const int maxn=20;
 7 ll dp[maxn][maxn];
 8 ll num[maxn][maxn];
 9 
10 int main()
11 {
12     int T,n,m,i,j,k,x,y,z;
13     char s[maxn];
14     scanf("%d",&T);
15     while ( T-- )
16     {
17         scanf("%s%d",s+1,&m);
18         n=strlen(s+1);
19         memset(dp,0,sizeof(dp));
20         for ( i=1;i<=n;i++ )
21         {
22             num[i][i]=s[i]-'0';
23             for ( j=i+1;j<=n;j++ ) num[i][j]=num[i][j-1]*10+s[j]-'0';
24         }
25         for ( i=1;i<=n;i++ ) dp[i][0]=num[1][i];
26         for ( j=1;j<m;j++ )
27         {
28             for ( i=1;i<=n;i++ )
29             {
30                 for ( k=1;k<i;k++ ) dp[i][j]=max(dp[i][j],dp[k][j-1]*num[k+1][i]);
31             }
32         }
33         printf("%lld\n",dp[n][m-1]);
34     }
35     return 0;
36 }

NYOJ746

 

 

Exercises:

1.(HDOJ4632)http://acm.hdu.edu.cn/showproblem.php?pid=4632

Given a string, ask how many palindrome substrings in this string (substrings can be discontinuous).

Analysis; dp[i][j] represents the number of palindrome substrings contained from I to j characters. Dp[i][i]=1 is initialized (because it itself is counted as a palindrome string), and other dp[i][j]=0.

dp[i][j]=(dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]+mod)%mod (Repulsion thought)

if ( s[i]==s[j] ) dp[i][j]+=dp[i+1][j-1]+1

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 typedef long long ll;
 6 const int maxn=1010;
 7 const int mod=10007;
 8 char s[maxn];
 9 int dp[maxn][maxn];
10 
11 int main()
12 {
13     int T,i,j,k,h,n,m,ans,len;
14     scanf("%d",&T);
15     for ( h=1;h<=T;h++ )
16     {
17         scanf("%s",s+1);
18         n=strlen(s+1);
19         memset(dp,0,sizeof(dp));
20         for ( i=1;i<=n;i++ ) dp[i][i]=1;
21         for ( len=2;len<=n;len++ )
22         {
23             for ( i=1;i<=n;i++ )
24             {
25                 j=i+len-1;
26                 if ( j>n ) break;
27                 dp[i][j]=(dp[i][j-1]+dp[i+1][j]-dp[i+1][j-1]+mod)%mod;
28                 if ( s[i]==s[j] ) dp[i][j]=(dp[i][j]+dp[i+1][j-1]+1+mod)%mod;
29             }
30         }
31         printf("Case %d: %d\n",h,dp[1][n]%mod);
32     }
33     return 0;
34 }

HDOJ4632

 

Leave a Reply

Your email address will not be published. Required fields are marked *