给出一个长度为N的序列，现在可以进行魔法操作，对于任意一个位置i，你可以将ai变为bi。光光比较喜欢单调递增的序列，请你输出最少的使用魔法次数，若不可能，输出-1。
一个整数N
接下来一行N个数:ai代表原数组的数
接下来一行N个数:bi代表原数组使用魔法后的数字。
ai对应bi
一个整数
将最后一个位置的2变为4 ，原序列 = [1,3,4]
#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int maxn=1e6+100; int a[maxn],b[maxn]; int dp[maxn][2]; int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i<=n;i++){ cin>>b[i]; } memset(dp,0x3f3f3f3f,sizeof(dp)); dp[1][1]=1; dp[1][0]=0; for(int i=2;i<=n;i++){ if(a[i]>a[i-1]){ dp[i][0]=min(dp[i][0],dp[i-1][0]); } if(a[i]>b[i-1]){ dp[i][0]=min(dp[i][0],dp[i-1][1]); } if(b[i]>a[i-1]){ dp[i][1]=min(dp[i][1],dp[i-1][0]+1); } if(b[i]>b[i-1]){ dp[i][1]=min(dp[i][1],dp[i-1][1]+1); } } if(dp[n][0]==0x3f3f3f3f&&dp[n][1]==0x3f3f3f3f){ cout<<-1<<endl; } else{ cout<<min(dp[n][0],dp[n][1])<<endl; } }
原文：https://www.cnblogs.com/lipu123/p/14489022.html