Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

Re:震惊!

Posted by 1843172768 at 2020-01-12 19:48:31 on Problem 1276
In Reply To:震惊! Posted by:1843172768 at 2020-01-12 15:43:10
> 别走!
> 我用的是单调队列优化的多重背包做法。
> 然后由于只需要上一层dp和记录当前层dp,我只开了dp[2][N]结果WA,我寻思没错啊。然后我开了dp[3][N]就AC了,这不是神经病吗???
> 下面是我的代码:
> 
> //#include<bits/stdc++.h>
> #include<cstdio>
> #include<algorithm>
> #include<cstring>  
> 
> using namespace std;
>     
> #define ll long long
> #define for1(i,a,b) for (int i=(a);i<=(b);i++)
> #define for0(i,a,b) for (int i=(a);i<(b);i++)
> #define rof1(i,a,b) for (int i=(a);i>=(b);i--)
> #define rof0(i,a,b) for (int i=(a);i>(b);i--)
> #define pb push_back
> #define fi first
> #define se second
> #define duozu int __T;scanf("%d",&__T);for1(ica,1,__T)
> void _W(const int &x) { printf("%d", x); }
> void _W(const ll &x) { printf("%I64d", x); }
> void _W(const double &x) { printf("%.16f", x); }
> void _W(const char &x) { putchar(x); }
> void _W(const char *x) { printf("%s", x); }
> void W(){}
> template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
> void _R(const int& x){ scanf("%d", &x); }
> void _R(const ll& x){ scanf("%I64d", &x); }
> void _R(const char* x){ scanf("%s", x); }
> void R(){}
> template<class T,class... U> void R(const T& head,const U& ...tail){_R(head);R(tail...);}
> const ll mod = 1e9+7;
> ll ft1(ll a,ll b){ll ans = 1;while (b){if (b&1) ans *= a;b>>=1,a*=a;}return ans;}
> ll ft2(ll a,ll b){ll ans = 1;while (b){if (b&1) ans = ans*a%mod;b>>=1,a=a*a%mod;}return ans;}
>     
> const int N = 1e5+5;
>     
> int l[N],r[N];
> 
> int dp[2][N];
> int v[N],w[N],n[N];
> 
> struct P{
>     int fi,se;
> }sta[N];
> 
> int main()
> {
>     int V,m;
> 
>     while (~scanf("%d %d",&V,&m)){
> 
>         memset(dp[0],0,sizeof(int)*(V+1));
>         memset(dp[1],0,sizeof(int)*(V+1));
> 
>         for1(i,1,m) R(n[i],w[i]),v[i] = w[i];
>         
>         int cur = 0,now = 1;
> 
>         for1(i,1,m){//前i件
>             for0(d,0,v[i]){//余数为d
>  
>                 int st=1,ed=0;
>                 for (int x=0;x*v[i]<=V;x++){//求dp[i][d+x*v] = sta[max(x-n[i]+1,0)~x] + x*w[i]
>                     int ww = dp[cur][d+x*v[i]] - x*w[i];
>                     while (st<=ed && ww>sta[ed].se) ed--;
>                     sta[++ed] = {x,ww};
>                     int border = max(x-n[i],0);
>                     while (st<=ed && sta[st].fi<border) st++;
>                     dp[now][d+x*v[i]] = sta[st].se + x*w[i];
>                 }
>             }
>             swap(cur,now);
>         }
>         W(dp[cur][V]);
> 
>     }
>     return 0;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator