自己看之区间DP

//菜鸡制作，看的时候可能三目运算符略烦;;;

区间DP入门题：Brackets

地址：http://59.77.139.92/Problem.jsp?pid=1463

分析（对区间DP的代码原理进行分步解析）：

 for(k=; k<L; k++)

 {

     for(i=, j=k; j<L; i++, j++)

     {

         if(s[i]=='['&&s[j]==']'||s[i]=='('&&s[j]==')')

             dp[i][j]=dp[i+][j-]+;

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

             dp[i][j]=max(dp[i][j], dp[i][x]+dp[x+][j]);

     }

 }

样例：（）（）（）

变量是一一对应的应该；

区间DP原理就可以理清楚了。

然后我们看一下这题：刺激的摩托飞艇

地址：http://59.77.139.92/Problem.jsp?pid=2382

这一题求最小拆除路线实际上就是求最大不相交路线的数量，也就是和上面那一题一模一样，但是这一题变通的地方在于dp数组一开始就要赋值，相连则dp[i][j]=1, 其他的地方完全可以照搬

 #include<stdio.h>

 #define max(a, b) a>b?a:b

 int n, i, j, k, l, dp[][], a;

 int main( )

 {

     scanf("%d", &n);

     while(n--)

         scanf("%d%d", &j, &k), j>k?dp[k][j]=:dp[j][k]=;

     for(k=, n=; k<n; k++)

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

         {

             for(l=i+, a=; l<j; l++)

                 a=max(a, dp[i][l]+dp[l][j]);

             dp[i][j]+=a;

         }

     printf("%d\n", dp[][]);

 }

例三：石子合并

地址：http://59.77.139.92/Problem.jsp?pid=2385

这一题的区别点就是石子是环状的，那么我们就可以简单的对数组进行延长操作来求，其他核心基本上不变

 #include<stdio.h>

 #define min(a, b) a<b?a:b

 int dp[][], i, j, k, l, n, a[], sum[];

 int main( )

 {

     scanf("%d", &n);

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

         scanf("%d", &a[i]), i?sum[i]=a[i]+sum[i-]:sum[i]=a[i];///sum数组记录前缀和

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

         a[i]=a[i-n], sum[i]=sum[i-]+a[i];///增长

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

         for(i=, j=k; j<*n; i++, j++)

             for(l=i, dp[i][j]=0x3f3f3f; l<j; l++)

                 dp[i][j]=min(dp[i][j], dp[i][l]+dp[l+][j]+sum[j]-sum[i-]);

     for(i=, j=0x3f3f3f; i<n; i++)

         if(j>dp[i][i+n-]&&dp[i][i+n-])

             j=dp[i][i+n-];

     printf("%d\n", j);

 }

巴特西

自己看之区间DP

最新文章

热门文章