QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#770675 | #2835. Number Theory | S00021 | TL | 92ms | 395448kb | C++14 | 1.3kb | 2024-11-21 23:15:12 | 2024-11-21 23:15:12 |
Judging History
answer
#include<bits/stdc++.h>
#define N 5005
#define pb push_back
#define fi first
#define INF 0x3f3f3f3f
#define se second
#define pii pair<int,int>
#define MP make_pair
using namespace std; const int B=5000;
int dp[N][N*2][2],a[N],c[N],n,T; char s[N];
bool chk(int x){ if(c[x+1]) return 1;
for(int i=x;i;i--) if(c[i]!=1) return c[i]>1;
return 1;
}int dfs(int x,int y,int z){
if(x==1) return abs(y-z*10);
if(abs(y)>5000) return INF;
if(~dp[x][y+B][z]) return dp[x][y+B][z];
int &ans=dp[x][y+B][z],w=a[x]-z*10; ans=INF;
if(x>5) for(int i=0;i<=1;i++) ans=min(ans,dfs(x-1,y-i,i)+abs(i+w)*x);
else{ int ww=(powl(10,x)-1)/9;
for(int i=0;i<=1;i++){
if(y>0) for(int j=0;j<=abs(y)/ww+1;j++) ans=min(ans,dfs(x-1,y-i-j*ww,i)+abs(i+w+j)*x);
else for(int j=0;j<=abs(y)/ww+1;j++) ans=min(ans,dfs(x-1,y-i+j*ww,i)+abs(i+w-j)*x);
}
}return ans;
}void slv(){
n=strlen(s+1); reverse(s+1,s+n+1);
memset(dp,-1,sizeof(dp)),memset(a,0,sizeof(a)),memset(c,0,sizeof(c));
for(int i=1;i<=n;i++) c[i]=s[i]-'0';
for(int i=n;i;i--){
while(chk(i)){
int t=min(max(c[i+1]*10+c[i]-1,1),9);
for(int j=1;j<=i;j++){
c[j]-=t; if(c[j]<0) c[j]+=10,c[j+1]--;
}a[i]+=t; }
}printf("%d\n",dfs(n+1,a[1],0));
}signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
while(~scanf("%s",s+1)) slv();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 92ms
memory: 395448kb
input:
12 100 998244353
output:
3 5 76
result:
ok 3 lines
Test #2:
score: -100
Time Limit Exceeded
input:
4296 5370 8014 9532 6311 4070 2541 4782 5630 1487 2916 454 2020 5650 1851 5885 3556 6533 5044 1780 5746 5605 7860 4416 4495 8081 2416 3534 6045 3348 4536 8725 3505 1074 1531 937 7954 4451 7052 9586 3468 2679 6085 9908 3630 8046 6282 2883 9021 1436 5201 8166 8986 2167 7780 4156 101 3753 5732 5173 118...