Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
19398 | 孙浩楠 | 加强版密码锁 | C++ | 通过 | 100 | 0 MS | 348 KB | 759 | 2021-05-15 17:15:29 |
#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; }