noip2006 总结

T1 能量项链

原题

在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为mrn（Mars单位），新产生的珠子的头标记为m，尾标记为n。

需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。

例如：设N=4，4颗珠子的头标记与尾标记依次为(2，3) (3，5) (5，10) (10，2)。我们用记号⊕表示两颗珠子的聚合操作，(j⊕k)表示第j，k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为：

(4⊕1)=1023=60。

这一串项链可以得到最优值的一个聚合顺序所释放的总能量为

((4⊕1)⊕2)⊕3）=1023+1035+10510=710。

输入输出格式

思路

将环解开，以2*n-1的长度平铺在桌上
设i，j为珠子的编号，f[i][j]表示合并i~j所有的珠子的最大能量，k表示断开的位置（即f[i][j]=f[i][k]+f[k][j]）
接下来枚举每一种可能的i~j的长度p和k，并更新最大值

代码

#include <cstdio>

#include <iostream>

#include <cstring>

#define RG register

using namespace std;

const int maxn=300+5;

inline int read()

{

    int x=0,w=1;

    char ch=0;

    ch=getchar();

    while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();

    if(ch=='-') w=-1,ch=getchar();

    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

    return x*w;

}

int n;

long long head[maxn],tail[maxn],f[maxn][maxn];

int main(){

    n=read();

    for(RG int i=1;i<=n;i++) head[i]=read();

    for(RG int i=1;i<n;i++) tail[i]=head[i+1];

    tail[n]=head[1];

    int m=n*2-1;

    for(RG int i=n+1;i<=m;i++){

        head[i]=head[i-n];

        tail[i]=tail[i-n];

    }

    memset(f,0,sizeof(f));

    for(RG int p=1;p<=n-1;p++)   //枚举长度

        for(RG int i=1;i<=m-1;i++){

            int j=i+p;             // i为头 j为尾

            if(j>m) break;

            for(RG int k=i;k<=j-1;k++){    //枚举每一种断开位置

                f[i][j]=max(f[i][k]+f[k+1][j]+head[i]*tail[k]*tail[j],f[i][j]);

            }

        }

    long long ans=0;

    for(RG int i=1;i<=n;i++) ans=max(ans,f[i][i+n-1]);  //从所有的断开位置中选出最大值

    printf("%lld\n",ans);

    return 0;

}

T2 金明的预算方案

原题

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：

思路

有条件的背包模型，可以枚举主件，有不取，取附件A，附件B，两个附件四种情况。

if j>=a[i,0] then f[j]:=max(f[j],f[j-a[i,0]]+a[i,0]*b[i,0]);//取主件

if j>=a[i,0]+a[i,1] then f[j]:=max(f[j],f[j-a[i,0]-a[i,1]]+a[i,0]*b[i,0]+a[i,1]*b[i,1]);//取第一个附件

if j>=a[i,0]+a[i,2] then f[j]:=max(f[j],f[j-a[i,0]-a[i,2]]+a[i,0]*b[i,0]+a[i,2]*b[i,2]);//取第二个附件

if j>=a[i,0]+a[i,1]+a[i,2] then f[j]:=max(f[j],f[j-a[i,0]-a[i,2]-a[i,1]]+a[i,0]*b[i,0]+a[i,2]*b[i,2]+a[i,1]*b[i,1]);//取三个附件

代码

#include<iostream>

using namespace std;

int main()

{

    int a,b,mx=0;

    int i,j;

    int m,n,v[61]={0},p[61]={0},q;

    int v1[61]={0},v2[61]={0},p1[61]={0},p2[61]={0};

    int f[50001]={0};

    cin>>m>>n;

    m/=10;

    for(i=1;i<=n;i++)

       {

            cin>>a>>b>>q;

            a/=10;

            if(q!=0)

            {

                    if(v1[q]==0){v1[q]=a;p1[q]=b;}

                    else {v2[q]=a;p2[q]=b;}

            }

            else {v[i]=a;p[i]=b;}

            }

    for(int i=1;i<=n;i++)

       for(int j=m;j>=v[i];j--)

          {

               f[j]=max(f[j],f[j-v[i]]+v[i]*p[i]);

               if(j-v1[i]-v[i]>=0)f[j]=max(f[j],f[j-v1[i]-v[i]]+v1[i]*p1[i]+v[i]*p[i]);

               if(j-v2[i]-v[i]>=0)f[j]=max(f[j],f[j-v2[i]-v[i]]+v2[i]*p2[i]+v[i]*p[i]);

               if(j-v1[i]-v2[i]-v[i]>=0)f[j]=max(f[j],f[j-v1[i]-v2[i]-v[i]]+v1[i]*p1[i]+v2[i]*p2[i]+v[i]*p[i]);

               mx=max(f[j],mx);

          }

          cout<<mx*10;

    //system("pause");

    return 0;

}

作业调度方案

原题

我们现在要利用m台机器加工n个工件，每个工件都有m道工序，每道工序都在不同的指定的机器上完成。每个工件的每道工序都有指定的加工时间。

每个工件的每个工序称为一个操作，我们用记号j-k表示一个操作，其中j为1到n中的某个数字，为工件号；k为1到m中的某个数字，为工序号，例如2-4表示第2个工件第4道工序的这个操作。在本题中，我们还给定对于各操作的一个安排顺序。

例如，当n=3，m=2时，“1-1，1-2，2-1，3-1，3-2，2-2”就是一个给定的安排顺序，即先安排第1个工件的第1个工序，再安排第1个工件的第2个工序，然后再安排第2个工件的第1个工序，等等。

一方面，每个操作的安排都要满足以下的两个约束条件。

对同一个工件，每道工序必须在它前面的工序完成后才能开始；

同一时刻每一台机器至多只能加工一个工件。

另一方面，在安排后面的操作时，不能改动前面已安排的操作的工作状态。

由于同一工件都是按工序的顺序安排的，因此，只按原顺序给出工件号，仍可得到同样的安排顺序，于是，在输入数据中，我们将这个安排顺序简写为“1 1 2 3 3 2”。

还要注意，“安排顺序”只要求按照给定的顺序安排每个操作。不一定是各机器上的实际操作顺序。在具体实施时，有可能排在后面的某个操作比前面的某个操作先完成。

例如，取n=3,m=2，已知数据如下：

则对于安排顺序“1 1 2 3 3 2”，下图中的两个实施方案都是正确的。但所需要的总时间分别是10与12。

当一个操作插入到某台机器的某个空档时（机器上最后的尚未安排操作的部分也可以看作一个空档），可以靠前插入，也可以靠后或居中插入。为了使问题简单一些，我们约定：

在保证约束条件（1）（2）的条件下，尽量靠前插入。并且，我们还约定，如果有多个空档可以插入，就在保证约束条件（1）（2）的条件下，插入到最前面的一个空档。于是，在这些约定下，上例中的方案一是正确的，而方案二是不正确的。显然，在这些约定下，对于给定的安排顺序，符合该安排顺序的实施方案是唯一的，请你计算出该方案完成全部任务所需的总时间。

格式

输入格式

输入文件的第1行为两个正整数，用一个空格隔开：

m n （其中m（<20）表示机器数，n（<20）表示工件数）

第2行：m*n个用空格隔开的数，为给定的安排顺序。

接下来的2n行，每行都是用空格隔开的m个正整数，每个数不超过20。

其中前n行依次表示每个工件的每个工序所使用的机器号，第1个数为第1个工序的机器号，第2个数为第2个工序机器号，等等。

后n行依次表示每个工件的每个工序的加工时间。

可以保证，以上各数据都是正确的，不必检验。

输出格式

输出文件只有一个正整数，为最少的加工时间。

样例1

样例输入

2 3

1 1 2 3 3 2

1 2

1 2

2 1

3 2

2 5

2 4

样例输出

思路

并无特殊算法，题目较难理解（这是一道语文题）

代码

#include <stdio.h>

const int maxn = 25;

int a[maxn*maxn], ord[maxn][maxn], time[maxn][maxn];

int vis[maxn*maxn][maxn*maxn], b[maxn], finish[maxn];

//vis表示用过的区间,注意数组问题

inline int Max ( int a, int b )

{

    return a > b ? a : b;

}

int main ( )

{

    //注意最重要的一句话：

    //同一个工件，每道工序必须在它前面的工序完成后才能开始

    int n, m, ans;

    //freopen ( "in0.in", "r", stdin );

    //freopen ( "in0.out", "w", stdout );

    scanf ( "%d%d", &m, &n );

    for ( int i = 0; i < n*m; i ++ )

    {

        scanf ( "%d", &a[i] );

        a[i] --;

    }

    for ( int i = 0; i < n; i ++ )

        for ( int j = 0; j < m; j ++ )

        {

            scanf ( "%d", &ord[i][j] );

            ord[i][j] --;

        }

    for ( int i = 0; i < n; i ++ )

        for ( int j = 0; j < m; j ++ )

            scanf ( "%d", &time[i][j] );

    ans = 0;

    for ( int i = 0; i < n*m; i ++ )

    {

        int t = a[i], j = b[t];

        int pos = finish[t]-1, k, sub = ord[t][j];

        //pos从此工序完成的起点-1开始,下面会加1

        do

        {

            pos ++;

            for ( k = 0; k < time[t][j]; k ++ )

                if ( vis[sub][pos+k] )

                {

                    pos = pos+k;

                    break ;

                }

        }while ( vis[sub][pos] );

        for ( int l = pos; l < pos+time[t][j]; l ++ )

            vis[sub][l] = 1;    //将这段区间标记

        ans = Max ( ans, pos+time[t][j] );  //找到最大时间

        finish[t] = pos+k;  //表示工序t完成需要的时间

        b[t] ++;

    }

    printf ( "%d", ans );

    return 0;

}

2^k进制数

原题

设r是个2k 进制数，并满足以下条件：

（1）r至少是个2位的2k 进制数。

（2）作为2k 进制数，除最后一位外，r的每一位严格小于它右边相邻的那一位。

（3）将r转换为2进制数q后，则q的总位数不超过w。

在这里，正整数k（1≤k≤9）和w（k<w≤30000）是事先给定的。

问：满足上述条件的不同的r共有多少个？

我们再从另一角度作些解释：设S是长度为w 的01字符串（即字符串S由w个“0”或“1”组成），S对应于上述条件（3）中的q。将S从右起划分为若干个长度为k 的段，每段对应一位2k进制的数，如果S至少可分成2段，则S所对应的二进制数又可以转换为上述的2k 进制数r。

例：

设k=3，w=7。则r是个八进制数（23=8）。由于w=7，长度为7的01字符串按3位一段分，可分为3段（即1，3，3，左边第一段只有一个二进制位），则满足条件的八进制数有：

2位数：高位为1：6个（即12，13，14，15，16，17），高位为2：5个，…，高位为6：1个（即67）。共6+5+…+1=21个。
3位数：高位只能是1，第2位为2：5个（即123，124，125，126，127），第2位为3：4个，…，第2位为6：1个（即167）。共5+4+…+1=15个。

所以，满足要求的r共有36个。

输入输出

输入

输入文件digital.in只有1行，为两个正整数，用一个空格隔开：

  k  W

输出

输出文件digital.out为1行，是一个正整数，为所求的计算结果，即满足条件的不同的r的个数（用十进制数表示），要求最高位不得为0，各数字之间不得插入数字以外的其他字符（例如空格、换行符、逗号等）。

（提示：作为结果的正整数可能很大，但不会超过200位）

样例

输入

3  7

输出

思路

题目中的那个从另一角度分析就已经蕴含了这个题的基本思路。就以题目的例子为例，长度为7位的01字串按3位一段就这样分：0 000 000。其中除了首段，每段都小于(111)2，也即小于2k，而首段自然是小于2w%k（对于w%k为0时也成立）了。

如果首段为0，则当这个2k进制数位数分别为2、3、…、[n/k]时，如果用b_max表示2k，对应的解的个数分别为C[b_max-1][2]、C[b_max-1][3]、…、C[b_max-1][n/k]（C[i][j]表示从i个数里选j个构成一组组合）。

如果首段不为0，设首段为x，则解就有c[b_max-x-1][n/k]个。

这样，求解的个数就搞定了，剩下的活就是高精了。求组合数可以用这个公式：C[n][m]=C[n-1][m-1]+C[n-1][m]，这样高精就只用加法了。

代码

#include<iostream>

using namespace std;

int k,n,bx,hx,ans[201];

int c[512][512][100];

void plus1(int x[],int y[],int z[])

{

    z[0]=max(x[0],y[0]);

    for(int i=1;i<=z[0];i++)

    {

        z[i]+=x[i]+y[i];

        z[i+1]+=z[i]/10;

        z[i]%=10;

    }

    if(z[z[0]+1]!=0)z[0]++;

}

void plus2(int x[],int y[])

{

    x[0]=max(x[0],y[0]);

    for(int i=1;i<=x[0];i++)

    {

        x[i]+=y[i];

        x[i+1]+=x[i]/10;

        x[i]%=10;

    }

    if(x[x[0]+1]!=0)x[0]++;

}

int main()

{

    cin>>k>>n;

    bx=1<<k;//2^k

    hx=1<<(n%k);

    for(int i=0;i<=bx;i++)

       for(int j=0;j<=i;j++)

       {

               if(j==0)c[i][j][0]=c[i][j][1]=1;

               else plus1(c[i-1][j],c[i-1][j-1],c[i][j]);

       }

    for(int i=2;i<=n/k&&i<bx;i++)plus2(ans,c[bx-1][i]);

    for(int i=1;i<hx&&n/k+i<bx;i++)plus2(ans,c[bx-i-1][n/k]);

    for(int i=ans[0];i>=1;i--)cout<<ans[i];

    cout<<endl;

    return 0;

}

巴特西