SRM 653 CountryGroupHard

题意:

  n 个人坐成一排,同一个国家的人坐在一起,记者问了一些人他们的国家有多少人,他们都回答了正确的信息。已知m条信息,每条信息形如第 pi 个位置上的人的国家有 ai 个人,求已知了这些信息能否推断出所有人所属国家的情况。

分析:

  f[i]表示到第i个位置,方案数是多少。然后枚举后面的多少人属于一个国家的。当f[i]>2的时候,设为2就行。初始化f[n]=1。

代码:

 /*
* @Author: mjt
* @Date: 2018-10-17 20:55:42
* @Last Modified by: mjt
* @Last Modified time: 2018-10-17 21:37:10
*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
#define fi(s) freopen(s,"r",stdin);
#define fo(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL; inline int read() {
int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;
for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;
} class CountryGroupHard{
public:
int f[];
string solve(vector <int> a) {
int n = a.size();
f[n] = ;
for (int i = n - ; i >= ; --i) {
if (a[i] == ) {
int ok = -;
for (int j = ; (i + j) <= n; ++j) {
if (a[i + j - ] != ) { // 最近的有数的位置
if (ok != - && ok != a[i + j - ]) break;
else ok = a[i + j - ];
}
if (ok == - || ok == j) f[i] += f[i + j];
}
}
else {
bool ok = (i + a[i] > n); // 要求后面的a[i]个相等
for (int j = i; j < n && j < i + a[i]; ++j)
if (a[j] && a[j] != a[i]) ok = true;
if (!ok) f[i] = f[i + a[i]];
}
if (f[i] >= ) f[i] = ;
}
return f[] > ? "Insufficient" : "Sufficient";
} };

最新文章

  1. Java基础--Java语言介绍
  2. dbms_output.put_line 不显示
  3. [MAC]2015款MACBOOK使用BOOTCAMP安装WIN8.1+多分区
  4. REST 风格的api
  5. c语言几种异常
  6. EasyUI-Tab 标签添加右键菜单
  7. git中reset与revert的使用
  8. IE8,9下的ajax缓存问题
  9. Kubernetes 概念整理
  10. io系列之常用流一
  11. POJ 3070(求斐波那契数 矩阵快速幂)
  12. 科普知识普及 - 桥接VS中继
  13. 十三 re模块
  14. windows 命令行出现中文乱码
  15. 前台报错:Uncaught TypeError: Cannot read property &#39;0&#39; of null
  16. bootstrap入门基础
  17. 【scrapy】其他问题2
  18. B树就想到这个
  19. High-Speed Tracking with Kernelized Correlation Filters(二)
  20. [mysql] Navicat for mysql_导入导出表结构

热门文章

  1. 协议森林09 爱的传声筒 (TCP连接)
  2. 关于使用Filter降低Lucene tf idf打分计算的调研
  3. C/C++——存储
  4. C#ref和out的区别-ref是有进有出,out是只出不进
  5. 6 spark 存储体系 --内存管理
  6. lwip BUG ,导致 系统 死机
  7. JNDI数据源(在Tomcat下配置JNDI多数据源实例)
  8. Instruments Time profiler 调优APP 之图片解码
  9. XML的序列化用法 vs平台开发
  10. webpack4.26的详细配置,包含babel, eslint, postcss, 及各种所需loader,内含大量注释