#include <cstdio> #include <cstring> #include <iostream> #include <vector> #include <algorithm> using namespace std; #define INF 1200000000 const int maxn = 5003; const int maxk = 1670; int d[maxn][2][maxk],v[maxn],n; bool vis[maxn][2][maxk]; int dp(int i,int j,int k){ if(vis[i][j][k]) return d[i][j][k]; vis[i][j][k] = true; if(k==0) return d[i][j][k]=0; int& ans=d[i][j][k]; ans=dp(i+2,1,k-1)+(v[i+1]-v[i+2])*(v[i+1]-v[i+2]); if(n-i-1>=k*3) ans=min(ans,dp(i+1,0,k)); return ans; } int main() { int T,k; scanf("%d",&T); while(T--){ scanf("%d %d",&k,&n); k+=8; for(int i=1;i<=n;i++) scanf("%d",&v[i]); for(int i=0;i<=n;i++) for(int j=0;j<2;j++) for(int kk=0;kk<=k;kk++) vis[i][j][kk]=false; printf("%d\n",dp(0,0,k)); } return 0; }
上面的版本是当时为了找到状态转移方程多加了一维,其实完全没必要
#include <cstdio> #include <cstring> #include <iostream> #include <vector> #include <algorithm> using namespace std; #define INF 1200000000 const int maxn = 5003; const int maxk = 1670; int d[maxn][maxk],v[maxn],n; bool vis[maxn][maxk]; int dp(int i,int k){ if(vis[i][k]) return d[i][k]; vis[i][k] = true; if(k==0) return d[i][k]=0; int& ans=d[i][k]; ans=dp(i+2,k-1)+(v[i+1]-v[i+2])*(v[i+1]-v[i+2]); if(n-i-1>=k*3) ans=min(ans,dp(i+1,k)); return ans; } int main() { int T,k; scanf("%d",&T); while(T--){ scanf("%d %d",&k,&n); k+=8; for(int i=1;i<=n;i++) scanf("%d",&v[i]); for(int i=0;i<=n;i++) for(int kk=0;kk<=k;kk++) vis[i][kk]=false; printf("%d\n",dp(0,k)); } return 0; }