QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#128807 | #6300. Best Carry Player 2 | lefy | WA | 1ms | 3724kb | C++14 | 1.2kb | 2023-07-21 15:54:11 | 2023-07-21 16:06:17 |
Judging History
answer
#include<bits/stdc++.h>
#define ll __int128
using namespace std;
int p[20],num[20];
ll dp[20][20][2],pw[19];
void sc(ll x){
int len=0;
do num[len++]=x%10;while(x/=10);
while(len--)putchar(num[len]+'0');
}
void solve(){
long long xx;int k;scanf("%lld%d",&xx,&k);
ll x=xx;
if(k==0){
ll ans=1;
while(x){
if(x%10!=9)break;
x/=10;ans*=10;
}
sc(ans);printf("\n");return;
}
int zero=0;
while(x%10==0)zero++,x/=10;
int m=0;
while(x){
p[++m]=x%10;x/=10;
}
for(int i=0;i<=19;i++)for(int j=0;j<=19;j++)dp[i][j][0]=dp[i][j][1]=1e18;
dp[0][0][0]=0;m=max(m,k);
// cout<<m<<"\n";
for(int i=1;i<=max(m,k);i++){
dp[i][0][0]=min(dp[i-1][0][0],dp[i-1][0][1]);
for(int j=1;j<=min(k,i);j++){
dp[i][j][0]=dp[i-1][j][0];
if(p[i]!=9)dp[i][j][0]=min(dp[i-1][j][1],dp[i][j][0]);
dp[i][j][1]=min(dp[i-1][j-1][0]+pw[i-1]*(10-p[i]),dp[i-1][j-1][1]+pw[i-1]*(9-p[i]));
// sc(pw[i-1]*(10-p[i]));cout<<" ";
// sc(dp[i][j][1]);cout<<" ";
// cout<<<<" "<<dp[i][j][1]<<"\n";
}
// cout<<"\n";
}
sc(min(dp[k][k][0],dp[k][k][1]));
while(zero--)printf("0");printf("\n");
}
int main(){
pw[0]=1;
for(int i=1;i<=18;i++)pw[i]=pw[i-1]*10;
int T;scanf("%d",&T);
while(T--)
solve();
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3724kb
input:
4 12345678 0 12345678 5 12345678 18 990099 5
output:
1 54322 999999999987654322 9901
result:
wrong answer 4th lines differ - expected: '9910', found: '9901'