跳跃式LIS(nlogn)，在普通的转移基础上增加一种可以跨越一段距离的转移，用一颗新的树状数组维护，同时，我们还要维护跨越完一次后面的转移，所以我用了3颗树状数组。。
比赛的时候一句话位置写错了，然后就。。。雪崩
呆马：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <vector> 6 #include <algorithm> 7 using namespace std; 8 int a[100][100]; 9 int sum,ans,num; 10 int t,n,m,x,y; 11 int dp[50][50][3002]; 12 int main() 13 { 14 scanf("%d",&t); 15 for (int k=1;k<=t;k++) 16 { 17 memset(a,0,sizeof(a)); 18 memset(dp,0,sizeof(dp)); 19 20 scanf("%d%d",&n,&m); 21 for(int i=1;i<=n;i++) 22 for (int j=1;j<=m;j++) 23 scanf("%d",&a[i][j]); 24 25 dp[1][1][a[1][1]]=a[1][1]*a[1][1]; 26 27 for (int i=1;i<=n;i++) 28 { 29 for (int j=1;j<=m;j++) 30 { 31 x=i-1; y=j-1; 32 if (i==1 && j==1) continue; 33 for (int k=1;k<=2000;k++) 34 { 35 if (dp[x][j][k]==0) continue; 36 sum=k+a[i][j]; 37 num=dp[x][j][k]+a[i][j]*a[i][j]; 38 if (dp[i][j][sum]==0) dp[i][j][sum]=num; 39 dp[i][j][sum]=min(dp[i][j][sum],num); 40 } 41 for (int k=1;k<=2000;k++) 42 { 43 if (dp[i][y][k]==0) continue; 44 sum=k+a[i][j]; 45 num=dp[i][y][k]+a[i][j]*a[i][j]; 46 if (dp[i][j][sum]==0) dp[i][j][sum]=num; 47 dp[i][j][sum]=min(dp[i][j][sum],num); 48 } 49 50 } 51 } 52 53 ans=999999999; 54 for (int i=1;i<=2000;i++) 55 { 56 if (dp[n][m][i]==0) continue; 57 num=(n+m-1)*dp[n][m][i]-i*i; 58 //cout<<i<<' '<<dp[n][m][i]<<' '<<num<<endl; 59 ans=min(ans,num); 60 } 61 printf("Case #%d: %d ",k,ans); 62 } 63 }