| ||||||||||
| 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