您的位置: 首页 > IT文章 > $NOIP2006$ 题解报告

$NOIP2006$ 题解报告

分类: IT文章 • 2025-01-22 11:48:01

目录

$Luogu P1063$ 能量项链$( √ )$

$Luogu P1064$ 金明的预算方案$( √ )$

$Luogu P1065$ 作业调度方案$( √ )$

$Luogu P1066$ $2^k$进制数$( √ )$

$Luogu P1063$ 能量项链

$DP$挺简单的，就$f[i][j]$表示从第$i$颗珠子合并到第$j$颗珠子的最大答案，暴力枚举转移即可

 1 #include<iostream>
 2 using namespace std;
 3 int head[205],tail[205],f[205][205]={0};
 4 int main(){
 5     int ans=0,n,i,t,j,k;
 6     cin>>n;
 7     for(i=1;i<=n;i++){cin>>head[i];head[i+n]=head[i];}
 8     for(i=1;i<=2*n-1;i++) tail[i]=head[i+1];tail[2*n]=head[1];
 9     for(i=1;i<=2*n-1;i++) f[i][i]=0;
10     for(t=1;t<=n-1;t++)
11       for(i=1;i<=2*n-t;i++){
12           j=i+t;
13           for(k=i;k<=j-1;k++)
14             f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+head[i]*tail[k]*tail[j]);
15       }
16     for(i=1;i<=n;i++) ans=max(ans,f[i][i+n-1]);
17     cout<<ans<<endl;
18     return 0;
19 }

代码戳这里

$Luogu P1064$ 金明的预算方案

题目传送门

我一开始看错题了$QAQ$，我以为一个主件可以有很多个附件

就考虑有这样几种选择，只选主件、选第一个附件、选第二个附件、选两个附件，$DP$还是很简单的

 1 #include<bits/stdc++.h>
 2 #define ri register int
 3 #define ll long long
 4 #define rl register ll
 5 #define go(i,a,b) for(ri i=a;i<=b;i++)
 6 #define back(i,a,b) for(ri i=a;i>=b;i--)
 7 #define g() getchar()
 8 #define il inline
 9 #define pf printf
10 #define mem(a,b) memset(a,b,sizeof(a))
11 using namespace std;
12 il int fr(){
13     ri w=0,q=1;char ch=g();
14     while(ch<'0'||ch>'9'){if(ch=='-')q=-1;ch=g();}
15     while(ch>='0'&&ch<='9')w=(w<<1)+(w<<3)+ch-'0',ch=g();
16     return w*q;
17 }
18 const int N=62;
19 const int M=32002;
20 int n,m,v[N],p[N],Q[N],f[M],ans,q[N][2];
21 int main(){
22     //freopen(".in","r",stdin);
23     //freopen(".out","w",stdout);
24     n=fr();m=fr();
25     go(i,1,m){
26         v[i]=fr(),p[i]=fr();Q[i]=fr();
27         if(Q[i]){
28             if(!q[Q[i]][0])q[Q[i]][0]=i;
29             else q[Q[i]][1]=i;
30         }
31     }
32     go(i,1,m){
33         if(Q[i])continue;
34         back(j,n,v[i]){
35             ri w=v[i]*p[i];
36             f[j]=max(f[j],f[j-v[i]]+w);
37             ri V=j-v[i],x=q[i][0],y=q[i][1];
38             if(x&&V>=v[x]){
39                 f[j]=max(f[j],f[V-v[x]]+w+v[x]*p[x]);
40                 if(y&&V>=v[y]){
41                     f[j]=max(f[j],f[V-v[y]]+w+v[y]*p[y]);
42                     if(V>=v[x]+v[y])f[j]=max(f[j],f[V-v[x]-v[y]]+w+v[x]*p[x]+v[y]*p[y]);
43                 }
44             }
45         }
46     }
47     go(i,1,n)ans=max(ans,f[i]);cout<<ans<<endl;
48     return 0;
49 }

代码戳这里

$Luogu P1065$ 作业调度方案

题目传送门

就模拟安排任务即可，因为总时间很短所以我们可以用一个数组记录当前这个时间是否有任务，然后要注意能安排任务的话肯定是要保证连续的这段时间都没有安排过任务$QAQ$

 1 #include<bits/stdc++.h>
 2 #define ri register int
 3 #define ll long long
 4 #define rl register ll
 5 #define go(i,a,b) for(ri i=a;i<=b;i++)
 6 #define back(i,a,b) for(ri i=a;i>=b;i--)
 7 #define g() getchar()
 8 #define il inline
 9 #define pf printf
10 #define mem(a,b) memset(a,b,sizeof(a))
11 using namespace std;
12 il int fr(){
13     ri w=0,q=1;char ch=g();
14     while(ch<'0'||ch>'9'){if(ch=='-')q=-1;ch=g();}
15     while(ch>='0'&&ch<='9')w=(w<<1)+(w<<3)+ch-'0',ch=g();
16     return w*q;
17 }
18 const int N=22;
19 int m,n,x[N*N],a[N][N],t[N][N],lst1[N],lst2[N],nw[N],ans;
20 bool vis[N][N*N];
21 int main(){
22     freopen("1.in","r",stdin);
23     //freopen("1.out","w",stdout);
24     m=fr();n=fr();
25     go(i,1,n*m)x[i]=fr();
26     go(i,1,n)go(j,1,m)a[i][j]=fr();
27     go(i,1,n)go(j,1,m)t[i][j]=fr();
28     go(x0,1,n*m){
29         nw[x[x0]]++;
30         ri now=nw[x[x0]],id=x[x0],nxt=lst1[id];
31         while(1){
32             while(vis[a[id][now]][nxt])nxt++;
33             ri net=nxt;
34             while(net<nxt+t[id][now]&&(!vis[a[id][now]][net]))net++;
35             if(net==nxt+t[id][now])break;nxt=net;
36         }
37         go(i,nxt,nxt+t[id][now]-1)vis[a[id][now]][i]=1;
38         lst1[id]=nxt+t[id][now];
39         lst2[a[id][now]]=max(lst2[a[id][now]],nxt+t[id][now]);
40     }
41     go(i,1,m)ans=max(ans,lst2[i]);pf("%d
",ans);
42     return 0;
43 }

代码戳这里

$Luogu P1066$ $2^k$进制数

题目传送门

我永远讨厌高精$×2$

用$dp$可以过，设$f[i][j]$表示$i$位数第$i$为$j$的方案数，$f[i][j]=sum_{k=j+1}^{mx-i+1}f[i-1][k]$。其中$mx$为$2^k-1$，然后我们就可以把数组第一维去掉，再用前缀和优化一下，当然我们的加法是高精加

 1 #include<bits/stdc++.h>
 2 #define ri register int
 3 #define ll long long
 4 #define rl register ll
 5 #define go(i,a,b) for(ri i=a;i<=b;i++)
 6 #define back(i,a,b) for(ri i=a;i>=b;i--)
 7 #define g() getchar()
 8 #define il inline
 9 #define pf printf
10 #define mem(a,b) memset(a,b,sizeof(a))
11 using namespace std;
12 il int fr(){
13     ri w=0,q=1;char ch=g();
14     while(ch<'0'||ch>'9'){if(ch=='-')q=-1;ch=g();}
15     while(ch>='0'&&ch<='9')w=(w<<1)+(w<<3)+ch-'0',ch=g();
16     return w*q;
17 }
18 const int N=(1<<9)+2;
19 int k,w,mx,f[N][202],ans[202];
20 il int add(int *a,int *b){//高精加
21     ri len=0,x=0;
22     while(len<a[0]||len<b[0]){
23         len++;a[len]+=b[len]+x;
24         x=a[len]/10;a[len]%=10;
25     }
26     if(x)a[++len]=x;
27     a[0]=len;return *a;
28 }
29 int main(){
30     freopen("1.in","r",stdin);
31     freopen("1.out","w",stdout);
32     k=fr();w=fr();
33     ri x=w/k,y=w%k,fst=0;
34     //x表示在2^k表示下能有多少位，y表示最高位的限制
35     go(i,1,y)fst+=1<<(i-1);//计算最高位最大为多少
36     mx=(1<<k)-1;
37     if(x==1||(x==2&&y==0)){//特判两位以内的情况
38         if(y==0)fst=mx;
39         ri sum=0;
40         go(i,1,fst)sum+=mx-i;
41         pf("%d
",sum);return 0;
42     }
43     go(i,1,mx-1){
44         f[i][1]=i;f[i][0]=1;
45         add(ans,f[i]);
46     }
47     go(i,3,x)go(j,1,mx-i+1){
48         add(f[j],f[j-1]);
49         add(ans,f[j]);
50     }
51     go(i,1,mx-x)add(f[i],f[i-1]);
52     back(i,mx-x,max(mx-x-fst+1,1))add(ans,f[i]);
53     //单独处理最高位
54     back(i,ans[0],1)pf("%d",ans[i]);puts("");
55     return 0;
56 }

代码戳这里

$NOIP2006$ 题解报告

目录

相关推荐