题解：P6457 [COCI2006-2007#5] IVANA

zjzx_wcj · 2024-06-21 18:12:52 · 题解

题解：P6457 [COCI2006-2007#5] IVANA

题目传送门

思路

经典的区间 dp（模板）。

由于题目里说是一条环，所以就可以自然的想到破环成链。

重点来了！！！

我们设 f_{i,j} 为第 i 个数到第 j 个数的这段区间。由于题目只需要奇偶数的判断，所以 a_i 只保留取余 2 的结果。接着来看可行条件：f_{i,i}-f_{i+1,i+n-1}>0。就是当先手能取出比后手更多的奇数时，方案数 +1。

代码参考

#include <bits/stdc++.h>
#define int long long
#define elif else if
#define fin(x) freopen (x,"r",stdin)
#define fout(x) freopen (x,"w",stdout)
#define rnt register int
#define reg(i,x,y) for (register int i=(x);i<=(y);++i)
#define Reg(i,x,y) for (register int i=(y);i>=(x);--i)
using namespace std;
namespace rwm {inline int read () {int s=0,w=0;char c=getchar ();while (!isdigit (c)){w|=(c=='-');c=getchar ();}while (isdigit (c)) {s=(s<<1)+(s<<3)+(c^48);c=getchar ();}return w?-s:s;}inline void write (int x) {if (x<0) putchar ( '-'),x=-x;if (x>9) write (x/10);putchar (x%10|48);}inline void writesp (int x) {write (x),putchar (' ');}inline void writeln (int x) {write (x),putchar ('\n');}inline int square (int x) {return x*x;}inline int floor (long double x) {return x;}inline int ceil (long double x) {return (int)(x+0.5);}inline int gcd (int x,int y) {int z=x%y;while (z) x=y,y=z,z=x%y;return y;}inline int lcm (int x,int y) {return x/gcd (x,y)*y;}};
using namespace rwm;
int n,ans,f[501][501];
signed main ()
{
    n=read ();
    reg (i,1,n) f[i][i]=f[i+n][i+n]=read ()%2;
    reg (d,2,n)
        reg (i,1,n*2)
        {
            int j=i+d-1;
            if (j>n*2) break;
            f[i][j]=max (f[i][i]-f[i+1][j],f[j][j]-f[i][j-1]);
        }
    reg (i,1,n)
        if (f[i][i]-f[i+1][i+n-1]>0) ++ans;
    write (ans);
    return 0;
}