首页 > 其他分享 >The 2022 ICPC Asia Hangzhou Regional Programming Contest C

The 2022 ICPC Asia Hangzhou Regional Programming Contest C

时间:2024-11-08 11:21:33浏览次数:1  
标签:Contest int sum Regional Programming ans mod dp define

C. No Bug No Game
\(很简单的一个dp\)
\(在枚举到当前为i的时候假设当前容量为j 对其进行转移\)

点击查看代码
#include<bits/stdc++.h>

#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int mod = 998244353;

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; };

int qpw(int a, int b) {
    int ans = 1;
    while (b) {
        if (b & 1)ans = ans * a % mod;
        a = a * a % mod, b >>= 1;
    }
    return ans;
}
int inv(int x) { return qpw(x, mod - 2); }
const int N=3e3+10;
int dp[N][N][5];
void solve(){
    int n,k;
    cin>>n>>k;
    int sum=0;
    vector p(n+1,vector<int>());
    for(int i=1;i<=n;i++){
        int t;
        cin>>t;
        sum+=t;
        p[i].resize(t+1);
        for(int j=1;j<=t;j++)cin>>p[i][j];
    }
    if(sum<=k){
//        assert(0);
        int ans=0;
        for(int i=1;i<=n;i++){
            int t=p[i].size()-1;
            ans+=p[i][t];
        }
        cout<<ans<<'\n';
        return;
    }
    memset(dp,~0x3f,sizeof dp);
    dp[0][0][1]=0;
    dp[0][0][0]=0;
    for(int i=1;i<=n;i++){
        int t=p[i].size()-1;
        for(int j=0;j<=k;j++){
            dp[i][j][0]=dp[i-1][j][0];
            dp[i][j][1]=dp[i-1][j][1];
            if(j>=t){
                dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j-t][0]+p[i][t]);
                dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j-t][1]+p[i][t]);
            }
            for(int z=1;z<t;z++){
                if(j>=z){
                    dp[i][j][0]=max(dp[i][j][0],dp[i-1][j-z][1]+p[i][z]);
                }
            }
        }
    }
    cout<<max(dp[n][k][1],dp[n][k][0])<<'\n';
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int _ = 1;
//    cin >> _;
    while (_--)solve();
}

标签:Contest,int,sum,Regional,Programming,ans,mod,dp,define
From: https://www.cnblogs.com/archer233/p/18534732

相关文章

  • The 2022 ICPC Asia Hangzhou Regional Programming Contest
    A.ModuloRuinstheLegend\(题目即求(sum+n*s+(n+1)*n/2*d)\equiv\modm的最小值\)\(由裴蜀定理可得n*s+(n+1)*n/2*d=gcd(n,(n+1)*n/2)\)\(令p=gcd(n,n*(n+1)/2)\)\(可以表示为(sum+k*p+t*m)\equiv\modm\)\(令g=gcd(p,m)\)\((sum+g*z)%m\)\(sum+g*z>=m时存在最小值\)\(......
  • AtCoder Beginner Contest 378 ——F
    https://atcoder.jp/contests/abc378/tasks/abc378_fhttps://atcoder.jp/contests/abc378/editorial/11307#include<bits/stdc++.h>#definexfirst#defineysecond#defineall(x)(x).begin(),(x).end()#definelowbit(x)(x)&-(x)usingnamespacestd;ty......
  • AtCoder Beginner Contest 284题解
    AtCoderBeginnerContest284A没有什么难点,反着输出一遍就可以了。#include<bits/stdc++.h>usingnamespacestd;stringa[2000];intmain(){ intn; cin>>n; for(inti=1;i<=n;i++)cin>>a[i]; for(inti=n;i;i--)cout<<a[i]<<'\n';......
  • AtCoder Beginner Contest 378
    ContestLink还得加练。A&B&C&D不具备任何思维含量。SubmissionASubmissionBSubmissionCSubmissionDE注意到它计算答案的式子,每个子区间和都需要取模,否则就是沙币题了,可以对于每个位置\(O(1)\)地统计答案扫过去然后\(\bmodM\)。常规地,记\(S_i=\sum......
  • 2024 CCPC Liaoning Provincial Contest
    tot:赛时是6题723罚时,还是差劲了。省赛,特别是这场省赛,难度低很多。前面4,5题都是签到题。第六题是一个关于闰年的容斥,脑子乱了,然后越来越绕。然后就没出。出的是一个诈骗题,题面引导你这是计算几何,但是实际上是简单dp,暴力o(n^2)预处理一下就行了。赛时还想着求凸包然后旋转卡壳求......
  • AtCoder Beginner Contest 360 - VP记录
    A-AHealthyBreakfast高桥日常出境。头一次知道getchar()的返回值是int。点击查看代码#include<cstdio>usingnamespacestd;intmain(){ chars[3]={getchar(),getchar(),getchar()}; if(s[0]=='R'&&s[1]=='M')puts("Yes"); els......
  • AtCoder Beginner Contest 378 E
    https://atcoder.jp/contests/abc378/tasks/abc378_ehttps://atcoder.jp/contests/abc378/editorial/11300#include<bits/stdc++.h>#definexfirst#defineysecond#defineall(x)(x).begin(),(x).end()#definelowbit(x)(x)&-(x)usingnamespacestd;ty......
  • AtCoder Beginner Contest 378
    AtCoderBeginnerContest378总结A直接模拟,存\(1\)到\(4\)出现个数。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<vector>#include<queue>#include<map&g......
  • MU5IN160 – Parallel Programming
    SorbonneUniversité–SESIM2——–MU5IN160–ParallelProgrammingHands-onSession6–DataflowforMotionApplicationVeryimportant,aboutthesubmissionofyourworkAttheendofthissessionyouwillhavetouploadthefollowingfilesonMoodle:1......
  • AtCoder Beginner Contest 378
    ABC378光速切掉前四题,结果倒在了第五题。A-Pairing难度:红。弱智题,不解释。#include<bits/stdc++.h>usingnamespacestd;intmain(){inta[5]={0};for(inti=1;i<=4;i++){intx;cin>>x;a[x]++;}intans=0;for(inti=1;i<=4;i++){......