首页 > 代码库 > NOIp DP 1003 爆零记
NOIp DP 1003 爆零记
6道DP题只拿了220分，NOIp我不滚粗谁滚粗？
考试历程貌似并没有什么可说的QAQ，就是不停的来回推方程和写崩的状态中。
正经题解
六道题其实除了第六道比较恶心..其他的都还算可以。
truck
水题，不多说。
1 //DP truck 2 //by Cydiater 3 //2016.10.3 4 #include <iostream> 5 #include <cstdio> 6 #include <cstdlib> 7 #include <cmath> 8 #include <ctime> 9 #include <iomanip>10 #include <cstring>11 #include <string>12 #include <algorithm>13 #include <queue>14 #include <map>15 using namespace std;16 #define ll long long17 #define db double18 #define up(i,j,n) for(int i=j;i<=n;i++)19 #define down(i,j,n) for(int i=j;i>=n;i--)20 #define FILE "truck"21 const int MAXN=1e3+5;22 const int oo=0x3f3f3f3f;23 inline int read(){24 char ch=getchar();int x=0,f=1;25 while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}26 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}27 return x*f;28 }29 int N,K;30 db R[MAXN],U[MAXN],C[MAXN],f[MAXN][MAXN],ans=0;31 namespace solution{32 void init(){33 N=read();K=read();34 up(i,0,K)scanf("%lf",&R[i]);35 up(i,0,K)scanf("%lf",&U[i]);36 up(i,0,K)scanf("%lf",&C[i]);37 }38 void DP(){39 memset(f,0,sizeof(f));40 up(i,1,N){41 up(j,1,K)f[i][j]=max(f[i][j],f[i-1][j-1]+R[j-1]-U[j-1]);42 up(j,0,K)f[i][1]=max(f[i][1],f[i-1][j]+R[0]-U[0]-C[j]);43 }44 }45 void output(){46 up(i,0,K)ans=max(ans,f[N][i]);47 cout<<ans<<endl;48 }49 }50 int main(){51 freopen(FILE".in","r",stdin);52 freopen(FILE".out","w",stdout);53 using namespace solution;54 init();55 DP();56 output();57 return 0;58 }
cleanup
很好的思路题。
当时写的时候还是太拿衣服了..，一眼DP方程$f[i]=min \{ f[j-1]+sum[i][j]^2 \}$。
这个平方呀，excited，再一眼数据范围，绝对是斜率优化（或者单调性优化），然后开始来回推方程。推到最后的时候悲惨的发现不满足斜率优化的条件，不甘心只拿暴力分（然而最后暴力分也没拿稳），又开始来回变形，无果。开始考虑单调性优化..两个小时过去了，无果。算了，随手码了个暴力，本来那个暴力是没问题的，后来写到第三题的时候加了个小优化QAQ，然后就炸了。
正解：
这个数据不管怎么给，答案不可能超过$N$（分$N$组即可）。所以最优解的每块对答案的贡献不可能超过$\sqrt{N}$，根据这个原理就可以对DP进行优化。
首先变形方程，$f[i]=min \{ f[b[j]-1]+j^2 \} j \in [1,\sqrt{N}]$，其中$b[j]$表示离$i$最近的（左），且满足$[b[j],i]$中不同的数字的个数不超过$j$个。
这时候我们如果能在$O(1)$的时间内求出$b[]$，就能在$O(N\sqrt{N})$的时间复杂度内求出本题答案。
如何在$O(1)$的时间内求出$b[]$?懒得说了，你搞个$pre[]$和$next[]$xjb搞搞就行了。
1 //NOIp DP cleanup 2 //by Cydiater 3 //2016.10.4 4 #include <iostream> 5 #include <cstdio> 6 #include <cstdlib> 7 #include <queue> 8 #include <map> 9 #include <ctime>10 #include <cmath>11 #include <iomanip>12 #include <algorithm>13 #include <cstring>14 #include <string>15 using namespace std;16 #define ll long long17 #define up(i,j,n) for(int i=j;i<=n;i++)18 #define down(i,j,n) for(int i=j;i>=n;i--)19 #define FILE "cleanup"20 const int MAXN=1e6+5;21 const int oo=0x3f3f3f3f;22 inline int read(){23 char ch=getchar();int x=0,f=1;24 while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}25 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}26 return x*f;27 }28 int N,M,a[MAXN],next[MAXN],tmp[MAXN],f[MAXN],lim,b[MAXN],pre[MAXN];29 namespace solution{30 void init(){31 N=read();M=read();32 memset(tmp,0,sizeof(tmp));33 up(i,1,N){34 a[i]=read();35 next[i]=tmp[a[i]];36 tmp[a[i]]=i;37 }38 memset(tmp,10,sizeof(tmp));39 memset(pre,10,sizeof(pre));40 down(i,N,1){41 pre[i]=tmp[a[i]];42 tmp[a[i]]=i;43 }44 lim=sqrt(1.0*N);45 }46 void DP(){47 memset(f,10,sizeof(f));48 memset(b,0,sizeof(b));49 f[0]=0;f[1]=1;b[1]=1;50 bool flag;51 up(i,2,N){52 flag=0;53 up(j,1,min(lim,i)){54 if(flag)break;55 if(b[j]!=0&&b[j+1]==0){56 if(next[i]<b[j])57 b[j+1]=b[j];58 flag=1;59 }60 if(next[i]>=b[j])continue;61 else{62 up(k,max(b[j],1),i-1)if(pre[k]>=i){63 b[j]=k+1;64 break;65 }66 }67 }68 up(j,1,min(lim,i))if(b[j]>0)f[i]=min(f[i],f[b[j]-1]+j*j);69 }70 }71 void output(){72 cout<<f[N]<<endl;73 }74 }75 int main(){76 freopen(FILE".in","r",stdin);77 freopen(FILE".out","w",stdout);78 using namespace solution;79 init();80 DP();81 output();82 return 0;83 }
wrk
水题，但是考场上写挂了，不说。
1 //DP wrk 2 //by Cydiater 3 //2016.10.3 4 #include <iostream> 5 #include <cstdio> 6 #include <cstring> 7 #include <string> 8 #include <algorithm> 9 #include <queue>10 #include <map>11 #include <ctime>12 #include <cmath>13 #include <iomanip>14 #include <cstdlib>15 using namespace std;16 #define ll long long17 #define up(i,j,n) for(int i=j;i<=n;i++)18 #define down(i,j,n) for(int i=j;i>=n;i--)19 #define FILE "wrk"20 const int MAXN=1e5+4;21 const int oo=0x3f3f3f3f;22 inline int read(){23 char ch=getchar();int x=0,f=1;24 while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}25 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}26 return x*f;27 }28 int T,S,N,f[10005][105],Time[MAXN],ans=0;29 struct Study{30 int m,l,a;31 }s[MAXN];32 namespace solution{33 void init(){34 T=read();S=read();N=read();35 up(i,1,S){36 s[i].m=read()+1;37 s[i].l=read();38 s[i].a=read();39 }40 memset(Time,10,sizeof(Time));41 up(i,1,N){42 int c=read();43 Time[c]=min(Time[c],read());44 }45 up(i,1,100)Time[i]=min(Time[i-1],Time[i]);46 }47 void slove(){48 memset(f,-1,sizeof(f));49 f[0][1]=0;50 up(i,0,T){51 up(j,1,100)if(f[i][j]>=0){52 if(i+Time[j]<=T)f[i+Time[j]][j]=max(f[i+Time[j]][j],f[i][j]+1);53 ans=max(ans,f[i][j]);54 }55 up(j,1,S)if(s[j].m==i+1&&i+s[j].l<=T&&f[i][j]>=0)f[i+s[j].l][s[j].a]=max(f[i+s[j].l][s[j].a],f[i][j]);56 }57 }58 }59 int main(){60 freopen(FILE".in","r",stdin);61 freopen(FILE".out","w",stdout);62 using namespace solution;63 init();64 slove();65 cout<<ans<<endl;66 return 0;67 }
exp
蛤省在11年省选的第一题，据说这一题稳妥A掉就进队了，弱省果然福利好....
其实这道题的关键不在于维护大小的关系，而在于维护相等的冲突。
首先，排除$x_i+y_i>N+1$这种显然不合法的情况，对于假设他们的值是从大到小排好序的，那么第$i$个人所属的区间显然就是$[x_i+1,N-y_i]$，也就是这个区间都是和这个人相等的人。
然后如果这个区间的人数大于这个区间的长度的话，那些超过的显然也是不合法的。
这时候问题就转化成了给你若干个区间，每个区间有一定的权值，要求用这些区间不重叠的覆盖线段且总权值和最大。到这里传统的DP就很容易解决了。
1 //NOIp DP exp 2 //by Cydiater 3 //2016.10.4 4 #include <iostream> 5 #include <algorithm> 6 #include <queue> 7 #include <map> 8 #include <ctime> 9 #include <cstdlib>10 #include <cmath>11 #include <cstdio>12 #include <cstring>13 #include <string>14 #include <iomanip>15 using namespace std;16 #define ll long long17 #define up(i,j,n) for(int i=j;i<=n;i++)18 #define down(i,j,n) for(int i=j;i>=n;i--)19 #define FILE "exp"20 const int MAXN=1e6+5;21 const int oo=0x3f3f3f3f;22 inline int read(){23 char ch=getchar();int x=0,f=1;24 while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}25 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}26 return x*f;27 }28 int N,LINK[MAXN],len=0,f[MAXN];29 struct edge{30 int y,next,v;31 }e[MAXN];32 namespace solution{33 inline void insert(int x,int y){34 for(int i=LINK[x];i;i=e[i].next)if(e[i].y==y){35 if(e[i].v<x-y+1)e[i].v++;36 return;37 }38 e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].v=1;39 }40 void init(){41 N=read();42 up(i,1,N){43 int x=read(),y=read();44 int leftt=x+1,rightt=N-y;45 if(x+y>=N)continue;46 insert(rightt,leftt);47 }48 }49 void DP(){50 memset(f,0,sizeof(f));51 up(i,1,N){52 f[i]=f[i-1];53 for(int j=LINK[i];j;j=e[j].next)f[i]=max(f[i],f[e[j].y-1]+e[j].v);54 }55 }56 void output(){57 cout<<N-f[N]<<endl;58 }59 }60 int main(){61 freopen(FILE".in","r",stdin);62 freopen(FILE".out","w",stdout);63 using namespace solution;64 init();65 DP();66 output();67 return 0;68 }
pyr
区间DP/分治 +乘法原理,很经典的一道题。
1 //NOIp pyr 2 //by Cydiater 3 //2016.10.3 4 #include <iostream> 5 #include <cstdio> 6 #include <cstdlib> 7 #include <cstring> 8 #include <string> 9 #include <algorithm>10 #include <queue>11 #include <map>12 #include <ctime>13 #include <cmath>14 #include <iomanip>15 using namespace std;16 #define ll long long17 #define up(i,j,n) for(int i=j;i<=n;i++)18 #define down(i,j,n) for(int i=j;i>=n;i--)19 #define FILE "pyr"20 const ll MAXN=1e3+5;21 const ll oo=0x3f3f3f3f;22 const ll mod=1000000000;23 inline int read(){24 char ch=getchar();int x=0,f=1;25 while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}26 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}27 return x*f;28 }29 char s[MAXN];30 ll N,f[MAXN][MAXN];31 namespace solution{32 void init(){33 scanf("%s",s+1);34 N=strlen(s+1);35 memset(f,-1,sizeof(f));36 }37 ll col(ll leftt,ll rightt){38 if(f[leftt][rightt]!=-1) return f[leftt][rightt];39 ll sum=0;40 if((rightt-leftt+1)%2==0) return 0;41 if(leftt==rightt) return 1;42 int mid=(leftt+rightt)>>1;43 bool flag=1;44 if(s[leftt]==s[rightt]){45 sum+=col(leftt+1,rightt-1);46 up(i,leftt+1,rightt-1)47 if(s[leftt]==s[i])48 (sum+=col(leftt+1,i-1)*col(i,rightt)%mod)%=mod;49 }50 f[leftt][rightt]=sum;51 return sum;52 }53 }54 int main(){55 freopen(FILE".in","r",stdin);56 freopen(FILE".out","w",stdout);57 //freopen("input.in","r",stdin);58 using namespace solution;59 init();60 cout<<col(1,N)<<endl;61 return 0;62 }
apo
考场上不会写的我只能现在写个题解了
1 //NOIp DP apo 2 //by Cydiater 3 //2016.10.4 4 #include <iostream> 5 #include <cstdlib> 6 #include <cstdio> 7 #include <cstring> 8 #include <string> 9 #include <algorithm>10 #include <queue>11 #include <map>12 #include <ctime>13 #include <iomanip>14 #include <cmath>15 using namespace std;16 #define ll long long17 #define up(i,j,n) for(ll i=j;i<=n;i++)18 #define down(i,j,n) for(ll i=j;i>=n;i--)19 #define FILE "apo"20 const ll MAXN=1e6+5;21 const ll oo=0x3f3f3f3f;22 const ll mod=(1<<31)-1;23 inline ll read(){24 char ch=getchar();ll x=0,f=1;25 while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}26 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}27 return x*f;28 }29 ll f[25][10],leftt,rightt,mid,T;30 namespace solution{31 void pret(){32 memset(f,0,sizeof(f));33 f[0][0]=1;34 up(i,1,21){35 f[i][3]=f[i-1][3]*10+f[i-1][2];36 f[i][2]=f[i-1][1];37 f[i][1]=f[i-1][0];38 f[i][0]=(f[i-1][0]+f[i-1][1]+f[i-1][2])*9;39 }40 }41 ll check(ll num){42 ll di=0,far=1,tmp=0,cnt=0,ans=0;43 for(;far<num;far*=10,di++);44 while(tmp<num){45 ll re_cnt;46 while(tmp+far<=num){47 tmp+=far;48 if(cnt==3) re_cnt=3;49 else if((tmp/far)%10==7) re_cnt=cnt+1;50 else re_cnt=0;51 down(i,3,3-re_cnt)ans+=f[di][i];52 }53 if(cnt!=3)cnt=((tmp/far)%10==6?cnt+1:0);54 di--;far/=10;55 }56 return ans;57 }58 ll slove(ll N){59 leftt=1;rightt=100000000000000000LL;60 N--;61 while(leftt+1<rightt){62 mid=(leftt+rightt)>>1;63 ll tmp=check(mid);64 if(tmp>N) rightt=mid;65 else leftt=mid;66 }67 if(check(leftt)==N) return leftt;68 return rightt;69 }70 }71 int main(){72 freopen(FILE".in","r",stdin);73 //freopen(FILE".out","w",stdout);74 using namespace solution;75 pret();76 T=read();77 while(T--)cout<<slove(read())<<endl;78 return 0;79 }
NOIp DP 1003 爆零记
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。