f[0]=1;
动规方程 f[i]=min(p1*f[x1],p2*f[x2],p3*f[x3]);
这题用long long 竟然WA
#include#include using namespace std; __int64 dp[600000]; __int64 Min(__int64 a,__int64 b,__int64 c) { a=min(a,b); return a=min(a,c); } int main() { __int64 i; __int64 p1,p2,p3,n; while(scanf("%I64d%I64d%I64d%I64d",&p1,&p2,&p3,&n)!=EOF) { __int64 x1,x2,x3; x1=x2=x3=0; dp[0]=1; for(i=1; i<=n; i++) { dp[i]=Min(p1*dp[x1],p2*dp[x2],p3*dp[x3]); if(dp[i]==dp[x1]*p1) x1++; if(dp[i]==dp[x2]*p2) x2++; if(dp[i]==dp[x3]*p3) x3++; } printf("%I64d\n",dp[n]); } }