Mike and gcd problem

挺有意思的一个题目,但是因为放在dp专题,所以在想怎么dp...还是不会dp,在网上也没找到dp的题解...
至于这题性质,脑袋编译了下,但是没继续深入证明把他们全部变成偶数即是最优解...
在这里阐述下证明..
首先假设它们的gcd()为1.那么怎么操作才能使得方案数最小呢?先对序列进行分类分奇偶..
首先序列全部为偶数,显然与假设不符..skip..
我们采用反证法,假设原序列的gcd为1,且不是全部转化成偶数最优.那么就一定是转化成了序列中的数含有某个奇数因子.假设不是一开始就含有这个奇数因子,那么就不可能通过转化得到,这个也是可以证明的.因为a+b/a-b都是不能提取关于a,b的那个奇数因子的.如此这个题目就证明完成了.
然后就只要贪心的进行偶数变化就行了.
先一次for把相邻为奇数的转化.第二次for把残余的奇数统计下就ok了..
ac代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=1e5+5;
int a[N];
bool b[N];
int main()
{
    int n;
    scanf("%d",&n);
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        cnt=__gcd(cnt,a[i]);
    }
    if(cnt!=1) {puts("YES");puts("0");return 0;}
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if((a[i]%2)&&(a[i-1]%2))
        {
            ans++;
            b[i-1]=b[i]=true;
            i++;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if((a[i]%2)&&!b[i])
        {
            ans+=2;
        }
    }
    puts("YES");
    cout<<ans<<endl;
    return 0;
}