Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:这道题明显的动态规划啊啊啊啊啊In Reply To:这道题明显的动态规划啊啊啊啊啊 Posted by:phython at 2017-06-22 22:59:01 > #include <iostream> > #include <algorithm> > #include <cstdio> > using namespace std; > int N,K; > const int MAX = 100005; > int dp[MAX]; > > int main(){ > cin>>N>>K; > for(int i = 0;i <= K;i++){ > dp[i] = abs((int)(N - i)); > } > for(int i = N+1;i <= K;i++){ > if(i & 1) // 奇数 > { > dp[i] = min(dp[i],dp[(i-1)/2]+2); > dp[i] = min(dp[i],dp[i-1]+1); > dp[i] = min(dp[i],dp[(i+1)/2]+2); > } > else{ > dp[i] = min(dp[i],dp[i/2]+1); > dp[i] = min(dp[i],dp[i-1]+1); > dp[i] = min(dp[i],dp[i/2 + 1]+2); > } > } > cout<<dp[K]<<endl; > return 0; > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator