Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:这道题明显的动态规划啊啊啊啊啊

Posted by 1803146326 at 2019-08-29 10:35:55 on Problem 3278
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator