bzoj3367[Usaco2004 Feb]The Big Game 球赛*
2024-09-05 10:50:06
bzoj3367[Usaco2004 Feb]The Big Game 球赛
题意:
n只奶牛,每只支持两个球队中的一个,它们依次上车,上到一定程度可以开走这辆车并换下一辆继续上。要求一辆车上支持不同球队的奶牛数的差≤I,或者这辆车上只有支持同一球队的牛。问通过安排换车时机所能得到的车数的最小值。n≤2500。
题解:
f[i]=f[j]+1,abs(sum[0][i]-sum[0][j]-sum[1][i]+sum[1][j])<=I||sum[0][i]==sum[0][j]||sum[1][i]==sum[1][j]。
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 2510
#define INF 0x3fffffff
using namespace std; inline int read(){
char ch=getchar(); int f=,x=;
while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}
while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();
return f*x;
}
int n,k,sum[][maxn],f[maxn]; char s[];
int main(){
n=read(); k=read();
inc(i,,n){
scanf("%s",s); sum[][i]=sum[][i-]; sum[][i]=sum[][i-];
if(s[]=='J')sum[][i]++;else sum[][i]++;
}
inc(i,,n){
f[i]=INF;
inc(j,,i-)if(abs(sum[][i]-sum[][j]-sum[][i]+sum[][j])<=k||sum[][i]-sum[][j]==||sum[][i]-sum[][j]==)
f[i]=min(f[i],f[j]+);
}
printf("%d",f[n]); return ;
}
20161116
最新文章
- Map的性能
- Android探索之BroadcastReceiver具体使用以及安全性探究
- java实现excel模板导出
- wpf直接绑定xml生成应用程序
- HashMap归档-超越昨天的自己系列
- 启动mysql错误ERROR 2002 (HY000): Can’t connect to local MySQL server through socket ‘/var/lib/mysql/mysql.sock’ (2)
- paip java.net.SocketException No buffer space available的解决办法及总结
- python数字图像处理(6):图像的批量处理
- (转)在 Windows 上安装Rabbit MQ 指南
- OpenCV 开发环境环境搭建(win10+vs2015+opencv 3.0)
- Sharepoint 弹出消息提示框 .
- ERP中文档权限设置:只能浏览不能下载?如何实现
- Java中String做为synchronized同步锁使用详解
- python一直放弃到双数的day10
- Python中包(package)的调用方式
- windows10 更新后要输入2次密码才能进入系统
- Quartz.net官方开发指南[转]
- [转]Hspice 语法手册
- .NET 4.0 中的契约式编程
- Uninstalling JIRA applications from Linux