hdu 4433 天津赛饮恨的c题·····事后才想出来

这题状态的设计主要在于后效性的消除，每步操作最多影响后面两位 然后预处理（枚举）出转移

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<sstream>
#include<string>
#include<climits>
#include<stack>
#include<set>
#include<bitset>
#include<cmath>
#include<deque>
#include<map>
#include<queue>
#define iinf 0x7f7f7f7f
#define linf 1000000000000000000LL
#define dinf 1e200
#define eps 1e-11
#define all(v) (v).begin(),(v).end()
#define sz(x)
x.size()
#define pb push_back
#define mp make_pair
#define lng long long
#define sqr(a) ((a)*(a))
#define pii pair<int,int>
#define pll pair<lng,lng>
#define pss pair<string,string>
#define pdd pair<double,double>
#define X first
#define Y second
#define pi 3.14159265359
#define ff(i,xi,n) for(int i=xi;i<=(int)(n);++i)
#define ffd(i,xi,n) for(int i=xi;i>=(int)(n);--i)
#define ffl(i,r) for(int i=head[r];i!=-1;i=edge[i].next)
#define ffe(i,r) for(_edge *i=head[r];i;i=i->next)
#define cc(i,j) memset(i,j,sizeof(i))
#define two(x)
((lng)1<<(x))
#define lson l , mid , rt << 1
#define rson mid + 1 , r , rt << 1 | 1
#define mod
1073741824
#define pmod(x,y) (x%y+y)%y
using namespace std;
typedef vector<int>
vi;
typedef vector<string>
vs;
template<class T> inline void checkmax(T &x,T y)
{
if(x<y) x=y;
}
template<class T> inline void checkmin(T &x,T y)
{
if(x>y) x=y;
}
template<class T> inline T Min(T x,T y)
{
return (x>y?y:x);
}
template<class T> inline T Max(T x,T y)
{
return (x<y?y:x);
}
template<class T> T Abs(T a)
{
return a>0?a:(-a);
}
template<class T> inline T lowbit(T n)
{
return (n^(n-1))&n;
}
template<class T> inline int countbit(T n)
{
return (n==0)?0:(1+countbit(n&(n-1)));
}
int num[10][10][10];
int dp[1010][10][10];
char a[1010],b[1100];
int d[6][3]= {1,0,0,9,0,0,1,1,0,9,9,0,1,1,1,9,9,9};
int main()
{
int c[6];
cc(num,0x7f);
for(c[0]=0; c[0]<=9; ++c[0])
for(c[1]=0; c[1]<=9; ++c[1])
for(c[2]=0; c[2]<=9; ++c[2])
for(c[3]=0; c[3]<=9; ++c[3])
for(c[4]=0; c[4]<=9; ++c[4])
for(c[5]=0; c[5]<=9; ++c[5])
{
int ds[3]= {};
int nu=0;
ff(i,0,5)
{
ff(j,0,2)
{
ds[j]+=c[i]*d[i][j];
}
nu+=c[i];
}
checkmin(num[ds[0]%10][ds[1]%10][ds[2]%10],nu);
}
while(scanf("%s%s",a+1,b+1)==2)
{
int n=strlen(a+1);
cc(dp,0x7f);
dp[0][0][0]=0;
ff(i,1,n)
{
int w=pmod(b[i]-a[i],10);
ff(j,0,9)
ff(k,0,9)
{
int ans=iinf;
ff(ij,0,9)
ff(ik,0,9)
{
checkmin(ans,dp[i-1][ij][ik]+num[pmod(w-ij,10)][pmod(j-ik,10)][k]);
}
dp[i][j][k]=ans;
}
}
int res=iinf;
ff(i,0,9)
ff(j,0,9)
checkmin(res,dp[n][i][j]);
printf("%dn",res);
}
return 0;
}

最后

以上就是可靠世界为你收集整理的hdu 4433 天津赛饮恨的c题·····事后才想出来的全部内容，希望文章能够帮你解决hdu 4433 天津赛饮恨的c题·····事后才想出来所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。