Hdu 5489 合肥网络赛 1009 Removed Interval

跳跃式LIS(nlogn)，在普通的转移基础上增加一种可以跨越一段距离的转移，用一颗新的树状数组维护，同时，我们还要维护跨越完一次后面的转移，所以我用了3颗树状数组。。

比赛的时候一句话位置写错了，然后就。。。雪崩

呆马：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <vector>

 #include <algorithm>

 using namespace std;

 int a[][];

 int sum,ans,num;

 int t,n,m,x,y;

 int dp[][][];

 int main()

 {

     scanf("%d",&t);

     for (int k=;k<=t;k++)

     {

         memset(a,,sizeof(a));

         memset(dp,,sizeof(dp));

         scanf("%d%d",&n,&m);

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

             for (int j=;j<=m;j++)

                 scanf("%d",&a[i][j]);

         dp[][][a[][]]=a[][]*a[][];

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

         {

             for (int j=;j<=m;j++)

             {

                 x=i-; y=j-;

                 if (i== && j==) continue;

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

                 {

                     if (dp[x][j][k]==) continue;

                     sum=k+a[i][j];

                     num=dp[x][j][k]+a[i][j]*a[i][j];

                     if (dp[i][j][sum]==) dp[i][j][sum]=num;

                     dp[i][j][sum]=min(dp[i][j][sum],num);

                 }

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

                 {

                     if (dp[i][y][k]==) continue;

                     sum=k+a[i][j];

                     num=dp[i][y][k]+a[i][j]*a[i][j];

                     if (dp[i][j][sum]==) dp[i][j][sum]=num;

                     dp[i][j][sum]=min(dp[i][j][sum],num);

                 }

             }

         }

         ans=;

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

         {

             if (dp[n][m][i]==) continue;

             num=(n+m-)*dp[n][m][i]-i*i;

             //cout<<i<<' '<<dp[n][m][i]<<' '<<num<<endl;

             ans=min(ans,num);

         }

         printf("Case #%d: %d\n",k,ans);

     }

 }

Removed Interval