codeforces 102263 J

题目

一开始贪心，直接枚举每个位置，一直wa，不知道错哪里了，后来才发现是dp，很多种情况是无法直接贪心的。

设 d p [ i ] [ 0 ] dp[i][0] dp[i][0]为直接从下往上统计且以第i位为结尾至少要用多少次， d p [ i ] [ 1 ] dp[i][1] dp[i][1]为从上往下统计。转移方程直接看代码好了，懒得写了。注意第i位从上往下转移且第i-1位也是从上往下转移时，必须要-2，有两个地方要减去，首先是i-1位可以少减一位，其次是第i位可以免去+10^x这个操作，例如77，模拟一下就懂了。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<set>
//#define int long long
using namespace std;
int dp[100005][5],n,k,x;
char s[100005];
int main()
{
	cin>>s+1;
	int len=strlen(s+1);
	dp[1][0]=s[1]-'0';
	dp[1][1]=1+10-(s[1]-'0');
	for(int i=2;i<=len;i++)
	{
		dp[i][0]=min(dp[i-1][0],dp[i-1][1])+s[i]-'0';
		dp[i][1]=min(dp[i-1][0]+11-(s[i]-'0'),dp[i-1][1]+9-(s[i]-'0'));
	}
	cout<<min(dp[len][0],dp[len][1]);
}