【NOIp】NOIp2006

ゝ一世哀愁。 2023-08-17 16:49 117阅读 0赞

# NOIp2006 #

### [T1 能量项链][T1] ###

标签：dp

区间dp，转移方程显然f\[i\]\[j\]=max(f\[i\]\[j\],f\[i\]\[k\]+f\[k\]\[j\]+a\[i\]\*a\[k\]\*a\[j\])

code

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 namespace gengyf{
     4     inline int read(){
     5         int x=0,f=1;char s=getchar();
     6         while(s<'0'||s>'9'){
         if(s=='-')f=-1;s=getchar();}
     7         while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
     8         return f*x;
     9     }
    10     int n,a[205],f[205][205],ans;
    11     int main(){
    12         n=read();
    13         for(int i=1;i<=n;i++){
    14             a[i]=read();a[i+n]=a[i];
    15         }
    16         for(int i=2;i<=n+1;i++){
    17             for(int l=1;l+i-1<=2*n;l++){
    18                 int r=l+i-1;
    19                 for(int k=l+1;k<=r-1;k++){
    20                     f[l][r]=max(f[l][r],f[l][k]+f[k][r]+a[l]*a[k]*a[r]);
    21                 }
    22             }
    23         }
    24         for(int i=1;i<=n;i++){
    25             ans=max(ans,f[i][n+i]);
    26         }
    27         printf("%d",ans);
    28         return 0;
    29     }
    30 }
    31 int main(){
    32     gengyf::main();
    33     return 0;
    34 }

### [T2 金明的预算方案][T2] ###

标签：背包

属于非树状有依赖的背包问题，先对每个主件的附件集合做01背包，再用分组背包求解全部的物品（[详见：洛谷P1064题解][P1064]

code

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 namespace gengyf{
     4     inline int read(){
     5         int x=0,f=1;char s=getchar();
     6         while(s<'0'||s>'9'){
         if(s=='-')f=-1;s=getchar();}
     7         while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
     8         return x*f;
     9     }
    10     struct bag{
    11         int v,p,q;
    12     }a[70],pat[70][70];
    13     int n,m,v[70][10],t[70],p[70][10],cnt[70],f[35000],ans;
    14     int main(){
    15         n=read();m=read();
    16         for(int i=1;i<=m;i++){
    17             a[i].v=read();a[i].p=read();a[i].q=read();
    18             if(a[i].q){
    19                 t[a[i].q]++;
    20                 pat[a[i].q][t[a[i].q]].v=a[i].v;
    21                 pat[a[i].q][t[a[i].q]].p=a[i].p;
    22                 pat[a[i].q][t[a[i].q]].q=a[i].q;
    23             }
    24         }
    25         for(int i=1;i<=m;i++){
    26             if(t[i]){
    27                 memset(f,-1,sizeof(f));
    28                 f[0]=0;
    29                 for(int j=1;j<=t[i];j++)
    30                     for(int k=n-a[i].v;k>=pat[i][j].v;k--){
    31                         if(f[k]<f[k-pat[i][j].v]+pat[i][j].v*pat[i][j].p && f[k-pat[i][j].v]!=-1){
    32                             f[k]=f[k-pat[i][j].v]+pat[i][j].v*pat[i][j].p;
    33                         }
    34                     }
    35                 for(int j=0;j<=n-a[i].v;j++){
    36                     if(f[j]!=-1){
    37                         cnt[i]++;
    38                         v[i][cnt[i]]=a[i].v+j;
    39                         p[i][cnt[i]]=f[j]+a[i].v*a[i].p;
    40                     }
    41                 }
    42             }
    43             if(!a[i].q){
    44                 cnt[i]++;
    45                 v[i][cnt[i]]=a[i].v;
    46                 p[i][cnt[i]]=a[i].p*a[i].v;
    47             }
    48         }
    49         memset(f,0,sizeof(f));
    50         for(int i=1;i<=m;i++)
    51             for(int j=n;j>=0;j--)
    52                 for(int k=1;k<=cnt[i];k++){
    53                     if(j>=v[i][k]){
    54                         f[j]=max(f[j],f[j-v[i][k]]+p[i][k]);
    55                     }
    56                 }
    57         for(int i=0;i<=n;i++){
    58             ans=max(ans,f[i]);
    59         }
    60         printf("%d",ans);
    61         return 0;
    62     }
    63 }
    64 int main(){
    65     gengyf::main();
    66     return 0;
    67 }

另附：[背包九讲][Link 1]

### [T3 作业调度方案][T3] ###

标签：模拟

这是一道语文题

首先注意他的读入文件中最后的2n行相当于两个n\*m的矩阵

第一个矩阵存的是每个工件的每个工序所使用的机器号

第二个存的是每个工件的每个工序的加工时间

因为没看到**接下来的2n行，每行都是用空格隔开的m个正整数，每个数不超过20**这句话卡了半个小时QwQ

不读题的后果

然后按题意模拟就行啦，具体解释见注释

code

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 namespace gengyf{
     4     inline int read(){
     5         int x=0,f=1;char s=getchar();
     6         while(s<'0'||s>'9'){
         if(s=='-')f=-1;s=getchar();}
     7         while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
     8         return x*f;
     9     }
    10     int order[500],mach[30][30],cost[30][30];
    11     //order 存第一行输入的顺序
    12     //mach 第一个矩阵中i个工件j道工序需要的机器
    13     //cost 第二个矩阵中i个工件j道工序所用的时间
    14     int n,m,ans;bool free[30][500];
    15     //free i号机器在第j分钟是否空闲
    16     int work[30],time[30],s;
    17     //work 第i个工件的工序数量
    18     //time 加工完第i个工件最晚的时间
    19     int main(){
    20         m=read();n=read();
    21         for(int i=1;i<=n*m;i++){
    22             order[i]=read();
    23         }
    24         for(int i=1;i<=n;i++)
    25             for(int j=1;j<=m;j++){
    26                 mach[i][j]=read();
    27             }
    28         for(int i=1;i<=n;i++)
    29             for(int j=1;j<=m;j++){
    30                 cost[i][j]=read();
    31             }
    32         for(int i=1;i<=n*m;i++){
    33             work[order[i]]++;
    34             for(int j=time[order[i]]+1;;j++){
         //看机器是否空闲
    35                 if(free[mach[order[i]][work[order[i]]]][j]==0){
    36                     s++;//如果空闲时间++
    37                 }
    38                 else s=0;
    39                 if(s==cost[order[i]][work[order[i]]]){
         //如果空闲的时间足够加工下一个
    40                     for(int k=j-s+1;k<=j;k++){
    41                         free[mach[order[i]][work[order[i]]]][k]=1;//那么这段时间就不空闲了
    42                     }
    43                     time[order[i]]=j;//这个工件的最晚时间为j
    44                     s=0;break;
    45                 }
    46             }
    47         }
    48         for(int i=1;i<=n;i++){
    49             ans=max(ans,time[i]);//取最晚的那个
    50         }
    51         printf("%d",ans);
    52         return 0;
    53     }
    54 }
    55 int main(){
    56     gengyf::main();
    57     return 0;
    58 }

### [T4 2^k进制数][T4 2_k] ###

标签：高精度，递推

f\[i\]\[j\]表示一个i位数第i位选j的方案数

f\[i\]\[j\]=$\{\\sum\_\{k=j+1\}^\{maxx-i+1\}\}$f\[i-1\]\[k\]

code

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 namespace gengyf{
     4     inline int read(){
     5         int x=0,f=1;char s=getchar();
     6         while(s<'0'||s>'9'){
         if(s=='-')f=-1;s=getchar();}
     7         while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
     8         return x*f;
     9     }
    10     int k,w,f[30005][201],ans[201];
    11     inline void add(int *a,int *b){
    12         int len=0,x=0;
    13         while(len<a[0]||len<b[0]){
    14             len++;
    15             a[len]=a[len]+b[len]+x;
    16             x=a[len]/10;
    17             a[len]%=10;
    18         }
    19         if(x>0)a[++len]=x;
    20         a[0]=len;
    21     }
    22     int main(){
    23         k=read();w=read();
    24         int m=w%k,l=w/k;
    25         int y=0;
    26         for(int i=1;i<=m;i++){
    27             y+=1<<(i-1);//最高位最大值
    28         }
    29         int maxx=(1<<k)-1;//第一位最大值
    30         if(l==1||(l==2&&m==0)){
         //特判两位的情况
    31             if(m==0)y=maxx;
    32             int tot=0;
    33             for(int i=1;i<=y;i++){
    34                 tot+=maxx-i;
    35             }
    36             printf("%d",tot);
    37             return 0;
    38         }
    39         for(int i=1;i<=maxx-1;i++){
         //递推
    40             f[i][1]=i;f[i][0]=1;
    41             add(ans,f[i]);
    42         }
    43         for(int i=3;i<=l;i++)
    44             for(int j=1;j<=maxx-i+1;j++){
    45                 add(f[j],f[j-1]);
    46                 add(ans,f[j]);
    47             }
    48         for(int j=1;j<=maxx-l;j++){
         //处理有限制的最高位
    49             add(f[j],f[j-1]);
    50         }
    51         for(int j=maxx-l;j>=max(maxx-l-y+1,1);j--){
    52             add(ans,f[j]);
    53         }
    54         for(int i=ans[0];i>=1;i--){
    55             printf("%d",ans[i]);
    56         }
    57         return 0;
    58     }
    59 }
    60 int main(){
    61     gengyf::main();
    62     return 0;
    63 }

--------------------

![1658269-20190901150233678-41202677.png][]

转载于:https://www.cnblogs.com/gengyf/p/11440178.html

[T1]: https://www.luogu.org/problem/P1063
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230809/cdfb001b24e64383812e3afc1f7debff.png
[T2]: https://www.luogu.org/problem/P1064
[P1064]: https://www.luogu.org/blog/shenyun/solution-p1064
[Link 1]: https://www.kancloud.cn/kancloud/pack/70131
[T3]: https://www.luogu.org/problem/P1065
[T4 2_k]: https://www.luogu.org/problem/P1066
[1658269-20190901150233678-41202677.png]: /images/20230809/4ceb33bb128b495b9db3ea55e9153c18.png