NOIPシミュレーション10.17単調キュー+ツリーDp+区間Dp

14949 ワード

NOIPシミュレーション

花火(fireworks.cpp/c/pas)【題目説明】町のメインストリートにはn個のエリアがあり、左から右に1からnと番号が付けられ、各エリア間には1単位距離が離れている.祝日にはm個の花火を打ち上げ、i番目の花火はti時刻のaiエリアで打ち上げます.ti時点であなたがいる領域がxであれば、bi-|ai-x|の快楽値を得ることができます.単位時間ごとにd単位距離を超えないように移動することができ、初期の位置は任意で、移動によって快楽値と最大値を得ることができます.【入力フォーマット】第1行の3つの整数n,m,d.次にm行、各行の3つの整数ai、bi、ti.【出力フォーマット】1行で、ハッピー値と最大値を得ることができます.【サンプル入力】10 2 1 1 1000 4 9 1000 4【サンプル出力】1992【データ範囲】30%のデータに対して、n<=100、m<=20.100%のデータに対して,1<=n<=150000,1<=m<=300,1<=d,ai<=n,1<=bi,ti<=10^9,i>=2に対してti>=ti−1があった.
dp[i][j]を第i期間のj位置での最大収益とする.jはdp[i-1]のある区間から移行することができるため、単調なキューでメンテナンスすることができる.複雑度n*m.

#include
#include
#include
#include
using namespace std;
typedef long long dnt;
const int maxn = 150005;
int n, m, d, last, cur, q[maxn];
dnt dp[2][maxn], a[305], b[305], tim[305], ans;
inline const dnt read(){
    register dnt  x = 0;
    register char ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x;
}
dnt calc(int pos, int sta){
    dnt ret = 0;
    int ti = tim[sta];
    for(int i = sta; tim[i] == ti && i <= m; ++i)
        ret += b[i] - abs(a[i] - pos);
    return ret;
}
int main(){
    freopen("fireworks.in", "r", stdin);
    freopen("fireworks.out", "w", stdout);
    n = read(), m = read(), d = read();
    for(int i = 1; i <= m; ++i)
        a[i] = read(), b[i] = read(), tim[i] = read();
    for(int i = 1; i <= m; ++i){
        if(tim[i] == tim[i - 1]) continue;
        last = cur, cur = cur ^ 1;
        int h = 1, t = 0;
        dnt lim = 1ll * (tim[i] - tim[i - 1]) * d;
        if(lim > n) lim = n;
        for(int j = 1; j <= n; ++j){
            while(h <= t && q[h] + lim < j) ++h;
            while(h <= t && dp[last][j] >= dp[last][q[t]]) --t;
            q[++t] = j;
            dp[cur][j] = dp[last][q[h]] + calc(j, i);
        }
        h = 1, t = 0;
        for(int j = n; j; --j){
            while(h <= t && q[h] - lim > j) ++h;
            while(h <= t && dp[last][j] >= dp[last][q[t]]) --t;
            q[++t] = j;
            dp[cur][j] = max(dp[cur][j], dp[last][q[h]] + calc(j, i));
        }
    }
    ans = dp[cur][1];
    for(int i = 2; i <= n; ++i) ans = max(dp[cur][i], ans);
    printf("%I64d
", ans);
}
/*
150000 2 2
1 1000 1
10000 2000 2
*/

ショッピング(shopping.cpp/c/pas)【テーマ説明】ショップにはn個の品物があり、i個目の品物の価格はci元です.品物は一度しか買えません.ショップではクーポンがn枚発行され、各品物に1枚ずつクーポンが発行されています.i枚目のクーポンを使えば、その品物をdi元安くすることができ、商品を買わなければ対応するクーポンを使うことができません.1枚目のクーポンは無条件で使用できますが、i>=2枚目のクーポンについては、i枚目のクーポンを使用する必要がある場合はxiというクーポンを先に使用する必要があります.今b元があって、最大いくらの商品を買うことができるかを聞きます.【入力フォーマット】第1行の2つの整数n,b.次にn行目、i行目に2つの整数ci,diがあり、i>=2の場合、3番目の整数xiが続く.【出力形式】1行、1つの整数は最も多く購入した商品の数を表す.【サンプル入力】8 9 4 3 8 3 3 1 1 1 4 2 7 2 2 3 1 2 7 3 1 2 7 3 3 3【サンプル出力】4【データ範囲】30%のデータに対してn<=100.100%のデータに対して、1<=n<=5000、1<=b<=10^9、1<=di=2に対して1<=xiツリーdp f[i][j][0/1]は、現在のiノードがj個の物品iを購入するためにクーポンを使用しない最小費用を示す.感じn^3、実はn^2です.各ノードは他のすべてのノードを更新することが多いからである.表面に隠されてはいけない.

#include
#include
using namespace std;
const int maxn = 5005;
int n, b, num, siz[maxn];
long long f[maxn][maxn][2];
int c[maxn], d[maxn], h[maxn];
struct edge{ int nxt, v;}e[maxn];
inline void add(int u, int v){ num++;e[num].v = v; e[num].nxt = h[u]; h[u] = num;}
void dfs(int u){
    for(int i = 0; i <= n; ++i) f[u][i][0] = f[u][i][1] = 2e18;
    f[u][1][1] = c[u] - d[u]; siz[u] = 1;
    f[u][0][0] = 0, f[u][1][0] = c[u];
    for(int p = h[u]; p; p = e[p].nxt){
        int v = e[p].v;
        dfs(v);
        for(int i = siz[u]; i >= 0 ; --i)
            for(int j = 0; j <= siz[v]; ++j){
                f[u][i + j][1] = min(f[u][i + j][1], f[u][i][1] + f[v][j][1]);
                f[u][i + j][1] = min(f[u][i + j][1], f[u][i][1] + f[v][j][0]);
                f[u][i + j][0] = min(f[u][i + j][0], f[u][i][0] + f[v][j][0]);
            }
        siz[u] += siz[v];
    }
}

int main(){
    freopen("shopping.in", "r", stdin);
    freopen("shopping.out", "w", stdout);   
    int x;
    scanf("%d%d", &n, &b);
    for(int i = 1; i <= n; ++i){
        scanf("%d%d", &c[i], &d[i]);
        if(i >= 2) scanf("%d", &x), add(x, i);  
    }
    dfs(1);
    for(int i = siz[1]; i >= 0; --i)
        if(f[1][i][1] <= b || f[1][i][0] <= b){
            printf("%d
", i);
            break;
        }
    return 0;
}

括弧マッチング(parenthesis.pas/cpp/c)【題名説明】長さNの括弧シーケンス((,),[,]のみを含む)を与え、これらの括弧のサブセットを削除する方法はいくつあるかを尋ね、残りの括弧シーケンスが合法的であるため、すべて削除できないことに注意してください.【入力フォーマット】入力された第1行は、シーケンスの長さを表す整数Nである.次の行のN文字は、括弧のシーケンスを表します.【出力フォーマット】シナリオ数モード1000000007の結果を示す行.【サンプル入力】4()[]【サンプル出力】3【データ範囲】30%のデータ保証:1<=N<=20.100%のデータ保証:1<=N<=300.
区間dp方案数は:合法括弧内の合法削除数*合法括弧外の合法削除数である.これで区間dpが可能になる.転移は明らかに2つの決定しかなく,l番目の括弧はマッチング(削除)せず,dp(l+1,r)に移行し,i番目の括弧とマッチングし,直接暴力列挙マッチングを行えばよい.

#include
#include
#define deeper(a) memset(a, -1, sizeof(a))
const int mod = 1000000007;
typedef long long dnt;
int n;
char s[305];
dnt f[305][305];
dnt dp(int l, int r){
    if(~f[l][r]) return f[l][r];
    if(l >= r) return 1;
    dnt& ret = f[l][r]; ret = 0;
    ret = dp(l + 1, r);
    char aim;
    if(s[l] == ')' || s[l] == ']') return ret % mod;
    if(s[l] == '(') aim = ')';
    if(s[l] == '[') aim = ']';
    for(int i = l + 1; i <= r; ++i)
        if(s[i] == aim)
            ret = (ret + dp(l + 1, i - 1) * dp(i + 1, r)) % mod;
    return ret % mod;
}
int main(){
    freopen("parenthesis.in", "r", stdin);
    freopen("parenthesis.out", "w", stdout);
    scanf("%d", &n);
    scanf("%s", s);
    deeper(f);
    printf("%I64d
", (dp(0, n - 1) - 1) % mod);
}

Opencvのlsdアルゴリズム

[筆記試験]常考アルゴリズム