Hongcow Buys a Deck of Cards CodeForces - 744C (状压)

时间:2022-09-17 00:09:51

大意: 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 (状压)的更多相关文章

  1. 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 ...

  2. Codeforces 744C Hongcow Buys a Deck of Cards 状压dp &lpar;看题解&rpar;

    Hongcow Buys a Deck of Cards 啊啊啊, 为什么我连这种垃圾dp都写不出来.. 不是应该10分钟就该秒掉的题吗.. 从dp想到暴力然后gg, 没有想到把省下的红色开成一维. ...

  3. Codeforces Round &num;385 &lpar;Div&period; 1&rpar; C&period; Hongcow Buys a Deck of Cards

    地址:http://codeforces.com/problemset/problem/744/C 题目: C. Hongcow Buys a Deck of Cards time limit per ...

  4. Codeforces 744C&period; Hongcow Buys a Deck of Cards(状压DP)

    这题的难点在于状态的设计 首先显然是个状压,需要一维表示卡的状态,另一维如果设计成天数,难以知道当前的钱数,没法确定是否能够购买新的卡,如果设计成钱数,会发现状态数过多,空间与时间都无法承受.但是可以 ...

  5. Codeforces 745E Hongcow Buys a Deck of Cards 状压DP &sol; 模拟退火

    题意:现在有n张卡片(n <= 16), 每一轮你可以执行两种操作中的一种.1:获得一张红色令牌和一张蓝色令牌.2:购买一张卡片(如果可以买的话),购买的时候蓝色卡片可以充当蓝色令牌,红色同理, ...

  6. 「CF744C」Hongcow Buys a Deck of Cards「状压 DP」

    题意 你有\(n\)个物品,物品和硬币有\(A\),\(B\)两种类型,假设你有\(M\)个\(A\)物品和\(N\)个\(B\)物品 每一轮你可以选择获得\(A, B\)硬币各\(1\)个,或者(硬 ...

  7. Vladik and cards CodeForces - 743E &lpar;状压&rpar;

    大意: 给定序列, 求选出一个最长的子序列, 使得任选两个[1,8]的数字, 在子序列中的出现次数差不超过1, 且子序列中相同数字连续. 正解是状压dp, 先二分转为判断[1,8]出现次数>=x ...

  8. codeforces 1185G1 状压dp

    codeforces 1185G1. Playlist for Polycarp (easy version)(动态规划) 传送门:https://codeforces.com/contest/118 ...

  9. CodeForces 11D&lpar;状压DP 求图中环的个数&rpar;

    Given a simple graph, output the number of simple cycles in it. A simple cycle is a cycle with no re ...

随机推荐

  1. Thinkphp 1&period;验证规则 2&period;静态定义 3&period;动态验证

    一.验证规则 数据验证可以对表单中的字段进行非法的验证操作.一般提供了两种验证方式: 静态定 义($_validate 属性)和动态验证(validate()方法). //验证规则 array( ar ...

  2. How to install the zsh shell in Linux &amp&semi;&amp&semi; 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 ...

  3. FbxDataType is ambiguous

    ??? 使用fbx自定义的类型的时候,比如 FbxIntDT 会有link error 根本原因是 FbxDataType is ambiguous solution: 把fbx的lib换成 libf ...

  4. Part 18 Indexes in sql server

    Indexes in sql server Clustered and nonclustered indexes in sql server Unique and Non Unique Indexes ...

  5. S5PV210启动过程分析

    一.三星官方推荐方式 1.数据手册<S5PV210_iROM_Application_note>中截取:

  6. iOS 通过UIControl,自定义控件

    如:自定义一个可以点击的 图文 #import <UIKit/UIKit.h> @interface UD_Button : UIControl @property(nonatomic,s ...

  7. React Native填坑之旅 -- 回归小插曲

    回归RN,非常开心啊! 在React Native 0.49.5上开发,直接遇到一个ios模拟器的问题.这个问题很简单就是Bundle URL not present. 在网上找了很多的解决方法,都不 ...

  8. socket(TCP)通讯之Python实现

    1.Service address = ('localhost', 9102) # AF_INET = ipv4; SOCK_STREAM:TCP s = socket.socket(socket.A ...

  9. 关于正则表达式的&OpenCurlyDoubleQuote;&bsol;b”

    今天刚刚开始看正则表达式就遇到一个十分头疼的问题,原文是这样的: “不幸的是,很多单词里包含hi这两个连续的字符,比如him,history,high等等.用hi来查找的话,这里边的hi也会被找出来. ...

  10. Parquet

     Parquet是列式存储格式的一种文件类型,列式存储有以下的核心优势: 可以跳过不符合条件的数据,只读取需要的数据,降低IO数据量压缩编码可以降低磁盘存储空间,由于同一列的数据类型是一样的,可以使用 ...