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

奇偶分别两个判断的dp

Posted by 1803146326 at 2019-08-29 10:37:45 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;#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int main()
{
	int s,e;
	cin>>s>>e;
	int a[100010]={0};
	for(int i = 0;i <= e;i++){
		a[i] = abs(s - i);
	}
	for(int i=s+1;i<=e;i++)
	{
		if(i%2==0)
		{
			a[i]=min(a[i],a[i-1]+1);
			a[i]=min(a[i],a[i/2]+1);
		}
		else
		{
			a[i]=min(a[i],a[i-1]+1);
			a[i]=min(a[i],a[(i+1)/2]+2);
		}
	}
	cout<<a[e]<<endl;
}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