Codeforces Round #385 //再遇状压
2024-10-09 01:31:27
敲完三题挂机一小时..... 也没懂DE什么意思 rank600上了一波分...
A. Hongcow Learns the Cyclic Shift
给一个字符串,每次可以把最后一个字符拿到开头 问能形成多少种..
暴力模拟 set去重...
判断矩形即可...
并查集求最大块 然后把未标记的块放进最大块里 最后的连边数-最初的 为我们添加的最多可能
交互题 第一次遇到 mk一下
E. Hongcow Buys a Deck of Cards
看不懂 ..... 特喵的又是个傻子状压..... 是时候总结一发 状压特征了
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
pii make(int x,int y)
{
return pii(x,y);
}
map<pii,int>dp[<<];
int n,r[],b[],c[];
void UMAX(int& x,int y){if(x<y) x=y;};
void UMIN(int& x,int y){if(x>y) x=y;};
int main()
{
scanf("%d",&n);
for(int i=;i<n;i++)
{
char ch[];
scanf("%s %d%d",ch,&r[i],&b[i]);
if(ch[]=='R') c[i] = ;
}
dp[][make(,)] = ;
map<pii,int>::iterator it;
for(int x=;x<(<<n);x++)
{
int re = ,bl = ;
for(int j=;j<n;j++)if((x>>j)&) c[j]?++re:++bl;
for(int j=;j<n;j++)
{
if(x&(<<j)) continue;
for(it = dp[x].begin();it!=dp[x].end();it++)
{
int nxt = (<<j)|x;
int cnt = ; //花费
int rv = max(r[j]-re,),bv = max(b[j]-bl,);
if(it->first.first<rv) UMAX(cnt,rv-it->first.first);
if(it->first.second<bv) UMAX(cnt,bv-it->first.second);
pii nxt_s = pii(it->first.first+cnt-rv,it->first.first+cnt-bv);
if(dp[nxt].count(nxt_s)==)dp[nxt][nxt_s] = INT_MAX;
UMIN(dp[nxt][nxt_s],cnt+it->second+);//1 为买操作
}
} }
int ans = INT_MAX;
for(it = dp[(<<n)-].begin();it!=dp[(<<n)-].end();it++)
{
UMIN(ans,it->second);
}
printf("%d\n",ans);
return ;
}
AC代码
最新文章
- JVM_七种垃圾收集器介绍
- 6个函数的output看JS的块级作用域
- 网络流量监控工具----iftop
- ActionResult,PartialViewResult,EmptyResult,ContentResult
- 禁止生成文件Thumbs.db
- JS里面匿名函数的调用 &; 变量作用域的实验
- JavaScript面向对象继承方法
- POJ3264——Balanced Lineup(线段树)
- C++静态成员函数和静态成员变量的探索
- asp.net跳出iframe结构转向登录
- PHPCMS V9 任意文件下载(Windows)
- 感觉不错的随笔 关于C、C++的
- LeetCode--032--最长有效括号(java)
- RK3399/NanoPC-T4开发板使用/sys/class/gpio操作外接GPIO设备-【申嵌视频-RK3399篇】
- 20175316盛茂淞 2018-2019-2 《Java程序设计》第2周学习总结
- odoo订餐系统之菜单设计
- LeetCode(57):插入区间
- JDK 之 NIO 2 WatchService、WatchKey(监控文件变化)
- Hive学习之路 (十三)Hive分析窗口函数(一) SUM,AVG,MIN,MAX
- hdu 5122 (2014北京现场赛 K题)