首页 > 代码库 > poj 3276
poj 3276
开关反转问题,想法很巧妙,看了一节课才看懂,严重怀疑自己弱智。。。。就难受
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> using namespace std; const int maxn=5000+10; int a[maxn],f[maxn];//B:1,F:0 int n; int fan(int k) { int sum=0,ans=0;//sum是待反转的数量 memset(f,0,sizeof(f)); for(int i=0;i+k<=n;i++)//注意这里是<=n,目的是预定最后一次反转 { if((sum+a[i])%2!=0)//最神奇的式子,只有出现要被反转的牛才成立,与sum-=f[i-k+1]呼应更新 { f[i]=1;//预定反转 ans++; } sum+=f[i]; if(i-k+1>=0) sum-=f[i-k+1];//反转,当然,只有f[i-k+1]=1才行,否则没什么卵用 } for(int i=n-k+1;i<n;i++) { if((sum+a[i])%2!=0)//最后反转一次后还需要再反转,就不成立了 return -1; if(i-k+1>=0) sum-=f[i-k+1]; } return ans; } int main() { scanf("%d",&n); for(int i=0;i<n;i++) { char cc; cin >> cc; if(cc==‘B‘) a[i]=1; else a[i]=0; } int k=1,m=n; for(int i=1;i<=n;i++) { int mm=fan(i); if(mm>=0&&mm<m)//更新最小次数 { m=mm; k=i; } } printf("%d %d\n",k,m); return 0; }
poj 3276
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。