| ||||||||||
| 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 | |||||||||
奇偶分别两个判断的dpIn 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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator