FZU 2041 checker(搜索)

题目链接:http://acm.fzu.edu.cn/problem.php?pid=2041

dir[i]存盘上可移动权值。

然后搜索就好。

水题。

AC代码:

#include<iostream>
#include<cstring>
using namespace std;
string str;
int dir[550];
int cas = 0;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int cnt = 0;
        int n,m;
        cin>>n>>m;
        cin>>str;
        int tp = -1,tpm=m;
        for(int i=0; i<n; i++)
        {
            if(str[i]=='1')
            {
                dir[cnt++]=i-tp-1;
                tp = i;
            }
        }
        dir[cnt++]=n-tp-1;
        int res=0;
        for(int i=0;i<cnt;i++)
        {
            m=tpm;
            int td=dir[i];
            for(int j=1;j<cnt;j++)
            {
               int ti=0;
               if(i>=j)ti+=dir[i-j];
               if(i<cnt-j)ti+=dir[j+i];
               int k=m/j<ti?m/j:ti;
               td+=k;
               m-=k*j;
               if(m<=0)break;
            }
            res=res>td?res:td;
        }
        cout<<"Case "<<++cas<<": "<<res<<endl;
    }
}

 

相关日志

  1. 2016.05.09

    FZU 2093 寻找兔子(状压dp)

    题目地址:http://acm.fzu.ed…

  2. 2016.05.09

    FZU 2091 播放器

    题目地址:http://acm.fzu.ed…

  3. 2016.07.13

    安利一波答案 经典算法设计

      (更多…)

  4. 2016.05.12

    ZOJ 3698 Carrot Fantasy(搜索大模拟)

    题目地址:http://acm.zju.ed…

  5. 2016.06.18

    竞赛技巧:读取一行到string类

    string类中定义了getline函数; …

  6. 2016.07.10

    Codeforces Round #361 (Div. 2)B. Mike and Shortcuts

    题意迷之简短。大意就是:一个城市i到另一个城…

评论

还没有评论。

在此评论中不能使用 HTML 标签。