https://vjudge.net/problem/POJ-3276
Farmer John has arranged his N (1 ≤ N ≤ 5,000) cows in a row and many of them are facing forward, like good cows. Some of them are facing backward, though, and he needs them all to face forward to make his life perfect.
Fortunately, FJ recently bought an automatic cow turning machine. Since he purchased the discount model, it must be irrevocably preset to turn K (1 ≤ K ≤ N)cows at once, and it can only turn cows that are all standing next to each other in line. Each time the machine is used, it reverses the facing direction of a contiguous group of K cows in the line (one cannot use it on fewer than K cows, e.g., at the either end of the line of cows). Each cow remains in the same *location* as before, but ends up facing the *opposite direction*. A cow that starts out facing forward will be turned backward by the machine and vice-versa.
Because FJ must pick a single, never-changing value of K, please help him determine the minimum value of K that minimizes the number of operations required by the machine to make all the cows face forward. Also determine M, the minimum number of machine operations required to get all the cows facing forward using that value of K.
Input
Lines 2.. N+1: Line i+1 contains a single character, F or B, indicating whether cow i is facing forward or backward.
Output
Sample Input
7 B B F B F B B
Sample Output
3 3
Hint
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<queue> #include<set> #include<algorithm> #include<map> #define maxn 200005 typedef long long ll; using namespace std; int n; int mp[maxn]; //牛的方向 0：F 1：B int vis[maxn]; //区间【i，i+k-1】是否需要反转 int fanzhuan(int x) { memset(vis,0,sizeof(vis)); int res=0; int sum=0; //vis数组的和 for(int i=0;i+x<=n;i++) //计算区间【i，i+k-1】 { if((mp[i]+sum)%2!=0) //判断是否需要反转 奇数需要反转 { res++; vis[i]=1; } sum+=vis[i]; if(i-x+1>=0) { sum-=vis[i-x+1]; } } //检查剩下的牛是否有面朝后的情况 for(int i=n-x+1;i<n;i++) { if((mp[i]+sum)%2!=0)return -1; if(i-x+1>=0) sum-=vis[i-x+1]; } return res; } int main() { char s[maxn]; while(scanf("%d",&n)!=EOF) { getchar(); for(int i=0;i<n;i++){ scanf("%c",&s[i]); getchar(); if(s[i]=='F')mp[i]=0; else mp[i]=1; } int K=1; int M=n; for(int k=1;k<=n;k++){ int ans=fanzhuan(k); if(ans>=0&&M>ans) { M=ans; K=k; } } printf("%d %d ",K,M); } return 0; }
POJ 3279
https://vjudge.net/problem/POJ-3279
Farmer John knows that an intellectually satisfied cow is a happy cow who will give more milk. He has arranged a brainy activity for cows in which they manipulate an M × N grid (1 ≤ M ≤ 15; 1 ≤ N ≤ 15) of square tiles, each of which is colored black on one side and white on the other side.
As one would guess, when a single white tile is flipped, it changes to black; when a single black tile is flipped, it changes to white. The cows are rewarded when they flip the tiles so that each tile has the white side face up. However, the cows have rather large hooves and when they try to flip a certain tile, they also flip all the adjacent tiles (tiles that share a full edge with the flipped tile). Since the flips are tiring, the cows want to minimize the number of flips they have to make.
Help the cows determine the minimum number of flips required, and the locations to flip to achieve that minimum. If there are multiple ways to achieve the task with the minimum amount of flips, return the one with the least lexicographical ordering in the output when considered as a string. If the task is impossible, print one line with the word "IMPOSSIBLE".
Input
Lines 2.. M+1: Line i+1 describes the colors (left to right) of row i of the grid with N space-separated integers which are 1 for black and 0 for white
Output
Sample Input
4 4 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1
Sample Output
0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0
题意：需要把所有的反转成0 求最少需要几步，，输出最少反转的解（字典序最小）
反转规则：每次反转一个的时候它的上下左右也要跟着反转
思路：从第一行开始反转 若第一行【i-1，j】需要反转则反转【i，j】
代码 复杂度 m*n*2^n
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<set>
#include<algorithm>
#include<map>
#define maxn 200005
typedef long long ll;
using namespace std;
int dx[5]={-1,0,0,0,1};
int dy[5]={0,-1,0,1,0};
int m,n,res; //m表示行 n表示列
int mp[105][105];
int mp1[105][105]; //保存最优解
int vis[105][105]; //保存中间结果
int get(int x,int y)
{
int c=mp[x][y];
for(int d=0;d<5;d++)
{
int x2=x+dx[d];
int y2=y+dy[d];
if(0<=x2&&x2<m&&0<=y2&&y2<n)
{
c+=vis[x2][y2];
}
}
return c%2;
}
// 不存在的话返回-1
int cacl()
{
//求出从第2行开始翻转的方法
for(int i=1;i<m;i++)
for(int j=0;j<n;j++)
{
if(get(i-1,j)!=0)
{
// (i-1,j)是黑色的话，必须反转这个格子
vis[i][j]=1;
}
}
//判断最后一行是否全白
for(int j=0;j<n;j++)
{
if(get(m-1,j)!=0)
return -1;
}
int res=0;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
{
res+=vis[i][j];
}
return res;
}
int main()
{
while(cin>>m>>n)
{
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
cin>>mp[i][j];
res=-1;
//按照字典序尝试第一行的所有可能性
for(int i=0;i<1<<n;i++)
{
memset(vis,0,sizeof(vis));
for(int j=0;j<n;j++){
vis[0][n-1-j]=i>>j&1;
}
int num=cacl();
if(num>=0&&(res<0||res>num))
{
res=num;
memcpy(mp1,vis,sizeof(vis));
}
}
if(res<0)
cout<<"IMPOSSIBLE"<<endl;
else {
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
{
printf("%d%c",mp1[i][j],j+1==n?' ':' ');
}
}
return 0;
}