提交时间:2021-05-12 19:08:03
运行 ID: 19244
#include<bits/stdc++.h> using namespace std; int a[1010],r[1010],dp1[110][110],dp[110][110]; int n,ans,tot,ma; void init() { cin>>n>>r[1]; for(int i=1;i<=n;++i){ a[i]=r[i]%100; r[i+1]=(r[i]*6807+2831)%201701; } } int check(int i,int j) { int mi=100; mi=min(mi,abs(a[i]-j)); mi=min(mi,abs(a[i]+100-j)); mi=min(mi,abs(j+100-a[i])); return mi*mi; } int main() { int i,j,k,ans=1<<30; init(); for(i=1;i<=n;++i){ for(j=0;j<=99;++j){ dp[i][j]=2000000; dp1[i][j]=check(i,j); } } for(j=0;j<=99;++j) dp[1][j]=dp1[1][j]; for(i=2;i<=n;++i) for(j=0;j<=99;++j) for(k=0;k<j;++k) dp[i][j]=min(dp[i][j],dp[i-1][k]+dp1[i][j]); for(j=0;j<=99;++j) ans=min(ans,dp[n][j]); cout<<ans; return 0; }