大意: n个红黑卡, 每天可以选择领取一块红币一块黑币, 或者买一张卡, 第$i$张卡的花费红币数$max(r_i-A,0)$, 花费黑币数$max(b_i-B,0)$, A为当前红卡数, B为当前黑卡数, 求买完所有卡最少天数.
这题挺巧妙的, 刚开始看花费的范围太大一直在想怎么贪心...
实际上注意到减费最多只有120, 可以按照减费进行dp即可
这题CF大神的最优解写了个模拟退火ORZ
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <math.h>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <string.h>
#include <bitset>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
//head const int N = 20;
int n;
char c[N];
int x[N], y[N];
int dp[1<<16][150];
void chkmax(int &a, int b) {a=max(a,b);}
int main() {
scanf("%d", &n);
REP(i,0,n-1) scanf(" %c%d%d", c+i, x+i, y+i);
memset(dp, 0xbc, sizeof dp);
dp[0][0] = 0;
int mx = (1<<n)-1;
REP(i,0,mx-1) {
int A = 0, B = 0;
REP(k,0,n-1) if (i>>k&1) {
if (c[k]=='R') ++A;
else ++B;
}
REP(k,0,n-1) if (!(i>>k&1)) {
REP(j,0,120) if (dp[i][j]!=0xbcbcbcbc) {
chkmax(dp[i^1<<k][j+min(x[k], A)],dp[i][j]+min(y[k], B));
}
}
}
int ans = INF, X = 0, Y = 0;
REP(i,0,n-1) X+=x[i], Y+=y[i];
REP(i,0,120) ans = min(ans, max(X-i, Y-dp[mx][i]));
printf("%d\n", ans+n);
}
Hongcow Buys a Deck of Cards CodeForces - 744C (状压)的更多相关文章
-
codeforces 744C Hongcow Buys a Deck of Cards
C. Hongcow Buys a Deck of Cards time limit per test 2 seconds memory limit per test 256 megabytes in ...
-
Codeforces 744C Hongcow Buys a Deck of Cards 状压dp (看题解)
Hongcow Buys a Deck of Cards 啊啊啊, 为什么我连这种垃圾dp都写不出来.. 不是应该10分钟就该秒掉的题吗.. 从dp想到暴力然后gg, 没有想到把省下的红色开成一维. ...
-
Codeforces Round #385 (Div. 1) C. Hongcow Buys a Deck of Cards
地址:http://codeforces.com/problemset/problem/744/C 题目: C. Hongcow Buys a Deck of Cards time limit per ...
-
Codeforces 744C. Hongcow Buys a Deck of Cards(状压DP)
这题的难点在于状态的设计 首先显然是个状压,需要一维表示卡的状态,另一维如果设计成天数,难以知道当前的钱数,没法确定是否能够购买新的卡,如果设计成钱数,会发现状态数过多,空间与时间都无法承受.但是可以 ...
-
Codeforces 745E Hongcow Buys a Deck of Cards 状压DP / 模拟退火
题意:现在有n张卡片(n <= 16), 每一轮你可以执行两种操作中的一种.1:获得一张红色令牌和一张蓝色令牌.2:购买一张卡片(如果可以买的话),购买的时候蓝色卡片可以充当蓝色令牌,红色同理, ...
-
「CF744C」Hongcow Buys a Deck of Cards「状压 DP」
题意 你有\(n\)个物品,物品和硬币有\(A\),\(B\)两种类型,假设你有\(M\)个\(A\)物品和\(N\)个\(B\)物品 每一轮你可以选择获得\(A, B\)硬币各\(1\)个,或者(硬 ...
-
Vladik and cards CodeForces - 743E (状压)
大意: 给定序列, 求选出一个最长的子序列, 使得任选两个[1,8]的数字, 在子序列中的出现次数差不超过1, 且子序列中相同数字连续. 正解是状压dp, 先二分转为判断[1,8]出现次数>=x ...
-
codeforces 1185G1 状压dp
codeforces 1185G1. Playlist for Polycarp (easy version)(动态规划) 传送门:https://codeforces.com/contest/118 ...
-
CodeForces 11D(状压DP 求图中环的个数)
Given a simple graph, output the number of simple cycles in it. A simple cycle is a cycle with no re ...
随机推荐
-
Thinkphp 1.验证规则 2.静态定义 3.动态验证
一.验证规则 数据验证可以对表单中的字段进行非法的验证操作.一般提供了两种验证方式: 静态定 义($_validate 属性)和动态验证(validate()方法). //验证规则 array( ar ...
-
How to install the zsh shell in Linux &;&; how to set it as a default login shell
Z shell’s (zsh) popularity has increased in the last years. I have not moved too zsh yet, but I am g ...
-
FbxDataType is ambiguous
??? 使用fbx自定义的类型的时候,比如 FbxIntDT 会有link error 根本原因是 FbxDataType is ambiguous solution: 把fbx的lib换成 libf ...
-
Part 18 Indexes in sql server
Indexes in sql server Clustered and nonclustered indexes in sql server Unique and Non Unique Indexes ...
-
S5PV210启动过程分析
一.三星官方推荐方式 1.数据手册<S5PV210_iROM_Application_note>中截取:
-
iOS 通过UIControl,自定义控件
如:自定义一个可以点击的 图文 #import <UIKit/UIKit.h> @interface UD_Button : UIControl @property(nonatomic,s ...
-
React Native填坑之旅 -- 回归小插曲
回归RN,非常开心啊! 在React Native 0.49.5上开发,直接遇到一个ios模拟器的问题.这个问题很简单就是Bundle URL not present. 在网上找了很多的解决方法,都不 ...
-
socket(TCP)通讯之Python实现
1.Service address = ('localhost', 9102) # AF_INET = ipv4; SOCK_STREAM:TCP s = socket.socket(socket.A ...
-
关于正则表达式的“\b”
今天刚刚开始看正则表达式就遇到一个十分头疼的问题,原文是这样的: “不幸的是,很多单词里包含hi这两个连续的字符,比如him,history,high等等.用hi来查找的话,这里边的hi也会被找出来. ...
-
Parquet
Parquet是列式存储格式的一种文件类型,列式存储有以下的核心优势: 可以跳过不符合条件的数据,只读取需要的数据,降低IO数据量压缩编码可以降低磁盘存储空间,由于同一列的数据类型是一样的,可以使用 ...