POJ 3666-MAking the Grade【線形dp】
1814 ワード
本題
タイトルリンク:http://poj.org/problem?id=3666
テーマの大意
与えられたシーケンスA,B.要求B厳格単調、要求最小化
S=∑Ni=1|Ai−Bi| S = ∑ N i = 1 | A i − B i |
問題を解く構想.
本の上の言う数学の帰納法によって、私達はSが最小化する条件の下で、きっと1種の構造のBの方案が存在することを証明することができて、Bの中の数値はすべてAの中で本の上の原話が現れたことがあります.fi,j f i,jは完了前のi個数を表し,Bi B iがj jのときの最小Sを表す.そして方程式を
fi,j=min{fi−1,k+|ai−j|}(k<=j) f i , j = m i n { f i − 1 , k + | a i − j | } ( k <= j )
しかし、これは非常に遅いので、変数で最小を記録することができます.
fi−1,kf−i−1,k,そしてA配列を離散化し,列挙の際に直接離散化後のAを用いる
code
タイトルリンク:http://poj.org/problem?id=3666
テーマの大意
与えられたシーケンスA,B.要求B厳格単調、要求最小化
S=∑Ni=1|Ai−Bi| S = ∑ N i = 1 | A i − B i |
問題を解く構想.
本の上の言う数学の帰納法によって、私達はSが最小化する条件の下で、きっと1種の構造のBの方案が存在することを証明することができて、Bの中の数値はすべてAの中で本の上の原話が現れたことがあります.fi,j f i,jは完了前のi個数を表し,Bi B iがj jのときの最小Sを表す.そして方程式を
fi,j=min{fi−1,k+|ai−j|}(k<=j) f i , j = m i n { f i − 1 , k + | a i − j | } ( k <= j )
しかし、これは非常に遅いので、変数で最小を記録することができます.
fi−1,kf−i−1,k,そしてA配列を離散化し,列挙の際に直接離散化後のAを用いる
code
#include
#include
using namespace std;
int n,ans,a[2001],b[2001],f[2001][2001],val;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),b[i]=a[i];
sort(b+1,b+1+n);//
ans=2147483647;
for(int i=1;i<=n;i++)
{
val=2147483647;
for(int j=1;j<=n;j++)
{
val=min(val,f[i-1][j]);//
f[i][j]=val+abs(a[i]-b[j]);//
if(i==n) ans=min(ans,f[i][j]);//
}
}
printf("%d",ans);
}