P1229 mine

Problem

http://acm.sjtu.edu.cn/OnlineJudge/problem/1229 Mine

Description

扫雷是一个很经典的小游戏,而一行数字一行雷的题目就更经典了。当然,这道题不能这么简单就算了。

问题是这样,有一个两行n列的格子,第一行里不会有雷,第二行里不会有数字。给定第一行的某些数字,数字代表该格子正下方与左右两个斜下方共三个格子里雷数目的总和。问下一行最多有多少个雷,并给出一个让雷尽可能靠后的方案(最后一个雷尽可能靠后,如果相同,倒数第二个雷尽可能靠后,以此类推)。保证一定存在一种合法的地雷安放方案。

Input Format

第一行一个整数n,表示格子的列数

第二行为一个长度为n的字符串,由‘0’、‘1’、‘2’、‘3’以及‘’组成。表示第一行的数字,‘’表示该格数字未定,保证不含其他字符(行末回车符除外)

Output Format

第一行为一个整数,表示最多的地雷数目

第二行为一个长度为n的字符串,由‘0’和‘1’组成,‘0’代表安全,‘1’代表有地雷。表示所要求的安放方案

Sample Input

2
1*

Sample Output

1
01

数据规模

10%数据 :1<=n<=10 40%数据 :1<=n<=100000,输入中不出现‘*’号 100%数据:1<=n<=100000

Analysis

dp一遍过。。。

用f[i][pre][now]表示前i位串,倒数第二位状态是pre,本位状态是now的最多地雷数。

f[i][pre][now] = 
max{ 
f[i-1][0][pre]+now    (if 0+pre+now == a[i-1] or a[i-1]=='*'),
f[i-1][1][pre]+now    (if 1+pre+now == a[i-1] or a[i-1]=='*')
}

初始

f[1][0][0]=0
f[1][0][1]=1

最后检验所有满足pre+now == a[n]的f[n][pre][now],取最大的一组。

注意,由于满足最右端最大,转移方程中应优先选择第二种情况,最后时候应优先选择01而不是10。

为了记录状态,开一个b[i][pre][now],表示在[i][pre][now]的情况下,f取得最大值时,i-2位应该取什么,这样在最后就能反向遍历了。

Code


/* **********************************
 * 精简版头文件  修改自岛娘的头文件
 * By lz96@foxmail.com
 * 复制到你的代码头部即可使用
 * **********************************/
#define T_ int  //各种循环变量的类型,特殊情况可以改成long long
#define fuck(s_) {cout<<s_<<endl;return 0;} //输出s_的内容并结束程序:fuck("NO");
/*************************
 * 各种循环函数
 * re:3个参数:循环变量,起始值,终止值
 * rep: 2个参数:循环变量,终止值/初始值
 * 后缀2/3:二维、三维
 * 后缀0:有则初始值/终止值为0 否则为1
 * 前缀r:有则从大到小循环,否则从小到大循环
 * ***********************/
#define printarr(a_,x_) rep(i_,x_)cout<<a_[i_]<<" ";cout<<endl; //输出一维数组 输出a[1] ~ a[5] printarr(a,5)
#define printarr0(a_,x_) rep0(i_,x_)cout<<a_[i_]<<" ";cout<<endl; // 输出a[0] ~ a[4] printarr0(a,5)
#define printarr2(a_,x_,y_) rep(i_,x_){rep(j_,y_)cout<<a_[i_][j_]<<' ';cout<<endl;} //输出二维数组
#define printarr20(a_,x_,y_) rep0(i_,x_){rep0(j_,y_)cout<<a[i_][j_]<<' ';cout<<endl;} //输出二维数组,下标从0开始
#define rep2o(a_,b_,n_) rep(a_,n_) re(b_,a_+1,n_) // for(T_ a_=1;a_<=n_;++a_) for(T_ b_=a_+1;b_<=n_;++b_)
#define rep20o(a_,b_,n_) rep0(a_,n_) re0(b_,a_+1,n_) // for(T_ a_=0;a_<n_;++a_) for(T_ b_=a_+1;b_<n_;++b_)
#define rep2(a_,b_,p_,q_) rep(a_,p_) rep(b_,q_)// for(T_ a_=1;a_<=n_;++a_) for(T_ b_=1;b_<=n_;++b_)
#define rep20(a_,b_,p_,q_) rep0(a_,p_) rep0(b_,q_) // for(T_ a_=0;a_<n_;++a_) for(T_ b_=0;b_<n_;++b_)
#define rrep2(a_,b_,p_,q_) rrep(a_,p_) rrep(b_,q_)
#define rrep20(a_,b_,p_,q_) rrep0(a_,p_) rrep0(b_,q_)
#define rep3(a_,b_,c_,p_,q_,r_) rep(a_,p_) rep(b_,q_) rep(c_,r_)
#define rep30(a_,b_,c_,p_,q_,r_) rep0(a_,p_) rep0(b_,q_) rep0(c_,r_)
#define rrep3(a_,b_,c_,p_,q_,r_) rrep(a_,p_) rrep(b_,q_) rrep(c_,r_)
#define rrep30(a_,b_,c_,p_,q_,r_) rrep0(a_,p_) rrep0(b_,q_) rrep0(c_,r_)
#define rep(a_,x_) re(a_,1,x_) //rep(i,5)   == for(T_ i=1;i<=5;++i)
#define rep0(a_,x_) re0(a_,0,x_) //rep0(i,5)   == for(T_ i=0;i<5;++i)
#define rrep(a_,x_) rre(a_,x_,1) //rrep(i,5)  ==  for(T_ i=5;i>=1;--i)
#define rrep0(a_,x_) rre(a_,x_-1,0) //rrep0(i,5)  ==  for(T_ i=4;i>=0;--i)
#define re(a_,s_,t_) for(T_ a_=s_;a_<=t_;++a_) // re(i,2,4)  ==   for(T_ i=2;i<=4;++i)
#define re0(a_,s_,t_) for(T_ a_=s_;a_<t_;++a_) // re0(i,2,4)  ==   for(T_ i=2;i<4;++i)
#define rre(a_,s_,t_) for(T_ a_=s_;a_>=t_;--a_)
#define rre0(a_,s_,t_) for(T_ a_=s_;a_>t_;--a_)
#define repit(a_,c_) for(__typeof__(a_.begin()) c_=a_.begin();c_!=a_.end();++c_) // 只在GCC上可用:repit(容器,迭代器)
#define nosync std::ios::sync_with_stdio(false);std::cin.tie(0);ios_base::sync_with_stdio(0) //加在main的第一行,加快输入输出,但之后不能用scanf/printf
#define DE false //是否在调试模式?
#define de(s_) if(DE){s_ } //  de(仅仅想在调试时执行的语句)     de(cout<<n<<m<<endl;)
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <numeric>
#include <bitset>
#include <fstream>
#include <iomanip>
#include <sstream>
#include <ctime>
#include <stack>
#include <queue>
#pragma GCC optimize("O2")
using namespace std;
#define endl '
'
const int dx4[] = {-1, 0, 1, 0};
const int dy4[] = {0, 1, 0, -1};  //十字方向的所有坐标 (basex+dx4[i] , basey+dy4[i])
const long long modb=100000007;  //取模的数  ModBase
const long inf=0x3f3f3f3f;      //很大的整数
const double oo=1e15;           //很大的实数
const double eps=1e-8;          //很小的实数,计算几何用
const double pi=acos(-1.0);     //pi
template<typename T> void clr(T* a_,int n_=0,size_t s_=-1) {if (s_==-1) s_=sizeof(a_); memset(a_,n_,sizeof(a_[0])*s_); }  // clr(a):将a清空为0     clr(a,0xff)将a每个字节清成0xff      clr(a,0xff,4) 将a[0]~a[3]的每一个字节填成0xff
template<typename T> T sqr(T a_) { return a_*a_; }  //平方
template<typename T> T cub(T a_) { return a_*a_*a_; }  //立方
inline T_ mf(T_ n_) {return ((n_<0)?n_+(modb<<3):n_)%modb; }  //mf(n) = n%modb,加上了负数判断,ModFunction
template<typename T>T max(T a_,T b_,T c_) { return max(a_,max(b_,c_)); } //三个参数的max
template<typename T>T min(T a_,T b_,T c_) { return min(a_,min(b_,c_)); } //三个参数的min
inline int dbcmp(double a_, double b_) { return (fabs(a_-b_)<eps)?0:(a_<b_?-1:1); } //允许误差的cmp,< : -1    == : 0    > : 1
inline double dbdiv(T_ a_, T_ b_) { return static_cast<double>(a_) / b_; } //实数除 dbdiv(3,5)=0.6
inline double angle(double x_, double y_) { if (x_==0.0) return y_>0?pi/2:3*pi/2; else { double t_=atan2(y_,x_); return (t_<0.0?t_+pi:t_) + y_<0?pi:0.0; }} //计算(x_,y_)的幅角 [0,2*pi)
/******************************************************************************************/
char a[100006];
bool b[100006][2][2];
int f[100006][2][2];
int n;
int main()
{
    nosync;
    cin>>n;
    rep(i,n)
        cin>>a[i];
    a[0]='*';
    a[n+1]='*';
    memset(f,0x9f,sizeof(f));
    f[1][0][1]=1;
    f[1][0][0]=0;
    re(i,2,n)
        rep0(pre,2)
        rep0(now,2)
        rep0(prepre,2)
        {
            if (a[i-1]=='*' || ((a[i-1]-'0') == pre+now+prepre))
              if (f[i-1][prepre][pre] +now >= f[i][pre][now])
              {
                  b[i][pre][now]=prepre;
                  f[i][pre][now] = f[i-1][prepre][pre] + now;
              }
        }
    stringstream s;
    int ans = -inf;
    rep0(now,2)
        rep0(pre,2) // 00 10 01 11
        if (a[n]=='*' || a[n]-'0' == now+pre)
        {
            if (f[n][pre][now]>=ans)
            {
                ans = f[n][pre][now];
                s.str("");
                s<<now<<pre;
                int p=b[n][pre][now], q=pre, step=n-1;
                while (step>1)
                {
                    s<<p;
                    int oldq=q;
                    q=p;
                    p=b[step][p][oldq];
                    step--;
                }
            }
        }
    cout<<ans<<endl;
    string w=s.str();
    rrep0(i, w.size())
        cout<<w[i];
}

发表评论