【题解】Making The Grade(DP+结论)

VJ:Making the Grade

HNOI-D2-T3 原题，禁赛三年。

或许是我做过的最简单的DP题了吧(一遍过是什么东西)

之前做过关于绝对值的题目，这种要求绝对值最小的题目，有一个很普遍的结论，最优解的集合中，一定有一个满足所有元素一定是所给定的元素中的元素，具体证明或许就是把括号拆开或者反证法吧。

然后就是这种看起来是\(O(n^3)\)的DP可以通过巧妙的实现降到\(O(n^2)\)，当然你暴力使用数据结构变成\(O(n^2\log n)\)也随便你(但是我暂时不会，因为还没有仔细思考，但求高手解答)。

考虑后面选择的内容和前面选择的内容是最优子结构，所以考虑DP

直接问什么求什么\(dp(i,j)\)表示对于第\(i\)个数字，我们拿\(j\)(数值)进行匹配，这样我们转移就太简单了

\[dp(i,j)=min\{dp(i-1,x|x<j)+|A_i-j|\}
\]

初始化什么的没有难度就不说了，然而值域很大，但是值域不影响转移，我们只关心大小，到时候统计答案的时候再还原就好了。

//@winlere

#include<iostream>

#include<cstring>

#include<cmath>

#include<cstdio>

#include<algorithm>

using namespace std;

typedef long long ll;

typedef unsigned int uint;

inline int qr(){

      register int ret=0,f=0;

      register char c=getchar();

      while(c<48||c>57) f|=c==45,c=getchar();

      while(c>=48&&c<=57) ret=ret*10+c-48,c=getchar();

      return f?-ret:ret;

}

const int maxn=2e3+5;

int n;

uint A[maxn];

uint sav[maxn];

int cnt;

ll dp[maxn][maxn];

inline ll retans(const ll&a,const ll&b){

      ll t1=a-b;

      if(t1<0)return -t1;

      return t1;

}

int main(){

#ifndef ONLINE_JUDGE

      freopen("in.in","r",stdin);

      freopen("out.out","w",stdout);

#endif

      n=qr();

      memset(dp,0x3f,sizeof dp);

      for(register int t=1;t<=n;++t)

	    sav[t]=A[t]=qr();

      sort(sav+1,sav+n+1);

      cnt=unique(sav+1,sav+n+1)-sav-1;

      for(register int t=1;t<=n;++t)

	    A[t]=lower_bound(sav+1,sav+cnt+1,A[t])-sav;

      memset(dp[0],0,sizeof dp[0]);

      for(register int t=1;t<=n;++t){

	    int mini=0;

	    for(register int i=1;i<=cnt;++i){

		  if(!mini || dp[t-1][mini]>dp[t-1][i]) mini=i;

		  dp[t][i]=min(dp[t][i],dp[t-1][mini]+retans(sav[A[t]],sav[i]));

		  //cout<<t<<' '<<i<<' '<<dp[t][i]<<' '<<mini<<endl;

	    }

      }

      ll ans=0xffffffffff;

      for(register int t=1;t<=cnt;++t)

	    ans=min(ans,dp[n][t]);

      cout<<ans<<endl;

      return 0;

}

巴特西

【题解】Making The Grade(DP+结论)

【题解】Making The Grade(DP+结论)

最新文章

热门文章