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
样例输出
10
思路
- 并无特殊算法，题目较难理解（这是一道语文题）
代码
#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
输出
36
思路
题目中的那个从另一角度分析就已经蕴含了这个题的基本思路。就以题目的例子为例，长度为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;
}
