题题题题
冰原狼
题目描述
冰原狼,也被称为黑狼,是特大而强大的狼。大部分的冰原狼来自德拉纳。狼群看起来像普通的狼,但这些生物的大小几乎是普通狼的两倍。这些强大的野兽有8 ~ 9英尺长,体重达到600 - 800磅,是最有名的兽人坐骑。这些大狼像人一样高,有着长长的颚骨,看起来好像可以咬断铁棒。他们有灼红的眼睛。冰原狼的皮毛有着斑驳的灰色或黑色的颜色。在卡利姆多北部地区和马尔戈尔,狼群茁壮成长。冰原狼狼群是非常高效的猎手,能够杀死他们捕获的任何东西。他们会在条件允许的时候,成群结队地包围并攻击敌人。
来自东方王国的冒险家马特,遇到一群可怕的冰原狼。有N匹狼站成一排(从左到右编号为1到N)。马特必须打败他们才能生存。一旦马特击败了一只可怕的狼,他将会遭受等同于当前这只狼的攻击值的伤害。而作为一群群居的野兽,每只狼i可以增加其相邻的狼bi的攻击。因此,每一个可怕的狼 i 的攻击值包括两个部分:其本身的基本攻击和来自相邻的狼的额外的攻击。增加的攻击值是暂时的,一旦当前这只狼被击败,它邻近的狼将不再从它得到额外的攻击值。然而,这两只狼(如果存在的话)当前就会彼此紧挨着。
例如,假设有3只冰原狼排成一排,它们的基本攻击分别是(3,5,7)。他们可以提供的额外攻击值 bi是 (8, 2, 0)。因此,它们目前的攻击值是(5、13、9)。如果马特先击败第二只狼,他将受到攻击值为13的伤害,活着的狼目前的攻击值就变成了(3,15)。
作为一个警觉和足智多谋的冒险家,马特可以决定他打败的冰原狼的顺序。因此,他想知道他打败所有的狼所必须遭受的最小伤害值是多少。
输入描述
第一行仅包含一个整数 T ,指示测试用例数。
对于每个测试用例,第一行仅包含一个整数 N(2 ≤ N ≤ 200)。
第二行包含 N 个整数ai (0 ≤ a i ≤ 100000),表示每只冰原狼的基本攻击值。
第三行包含 N 个整数 bi (0 ≤b i≤ 50000),表示每只冰原狼可以提供的额外攻击值。
输出描述
对于每个测试用例,输出一行"case #x:y",其中 x 是样例的编号(从 1 开始),y 是马特需要承担的最小伤害值。
样例
输入
2 3 3 5 7 8 2 0 10 1 3 5 7 9 2 4 6 8 10 9 4 1 2 1 2 1 4 5 1
输出
Case #1: 17 Case #2: 74
提示
在第一个样例中,马特从左到右打败了冰原狼。 他受到5 + 5 + 7 = 17点伤害,这是他必须承受的最少伤害。
代码
- #include
- #include
- #include
- #include
- using namespace std;
- int t,n,a[1005],b[1005],f[1005][1005],g=0;
- int main(){
- cin>>t;
- while(t--){
- cin>>n;
- g++;
- for(int i=1;i<=n;i++){
- cin>>a[i];
- }
- for(int i=1;i<=n;i++){
- cin>>b[i];
- }
- memset(f,0,sizeof f);
- b[0]=b[n+1]=0;
- for(int i=1;i<=n;i++){
- f[i][i]=a[i]+b[i-1]+b[i+1];
- }
- for(int l=1;l<=n;l++){
- for(int i=1;i<=n;i++){
- int j=i+l-1;
- f[i][j]=0x3f3f3f3f;
- for(int k=i;k<=j;k++){
- f[i][j]=min(f[i][j],f[i][k-1]+f[k+1][j]+a[k]+b[i-1]+b[j+1]);
- }
- }
- }
- cout<<"Case #"<
": "<1][n]<<"\n"; - }
- return 0;
- }
自然数的拆分求方案数
题目类型:完全背包
题目描述
给定一个自然数N,要求把N拆分成若干个正整数相加的形式,参与加法运算的数可以重复。注意:拆分方案不考虑顺序;至少拆分成2个数的和。 1≤N≤4000
求拆分的方案数 mod2147483648 的结果。
输入描述
一个自然数N。
输出描述
输入一个整数,表示结果。
样例
输入
7
输出
14
提示
1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+1+3
1+1+1+2+2
1+1+1+4
1+1+2+3
1+1+5
1+2+2+2
1+2+4
1+3+3
1+6
2+2+3
2+5
3+4(共14行)
代码
- #include
- using namespace std;
- #define ll long long
- int n,f[40005];
- int main(){
- cin>>n;
- f[0]=1;
- for(int i=1;i
- for(int j=i;j<=n;j++){
- f[j]=f[j]+f[j-i];
- f[j]%=2147483648;
- }
- }
- cout<
- return 0;
- }
货币系统
题目描述
在网友的国度中共有 n 种不同面额的货币,第 i 种货币的面额为 a[i],你可以 假设每一种货币都有无穷多张。为了方便,我们把货币种数为 n、面额数组为 a[1..n] 的货币系统记作 (n,a)。
在一个完善的货币系统中,每一个非负整数的金额 x 都应该可以被表示出,即对 每一个非负整数 x,都存在 n 个非负整数 t[i] 满足 a[i]× t[i] 的和为 x。然而, 在网友的国度中,货币系统可能是不完善的,即可能存在金额 x 不能被该货币系统表 示出。例如在货币系统 n=3, a=[2,5,9] 中,金额 1,3 就无法被表示出来。
两个货币系统 (n,a) 和 (m,b) 是等价的,当且仅当对于任意非负整数 x,它要 么均可以被两个货币系统表出,要么不能被其中任何一个表出。
现在网友们打算简化一下货币系统。他们希望找到一个货币系统 (m,b),满足 (m,b) 与原来的货币系统 (n,a) 等价,且 m 尽可能的小。他们希望你来协助完成这 个艰巨的任务:找到最小的 m。
输入描述
输入文件名为 money.in。
输入文件的第一行包含一个整数 T,表示数据的组数。接下来按照如下格式分别给 出 T 组数据。
每组数据的第一行包含一个正整数 n。接下来一行包含 n 个由空格隔开的正整数 a[i]。
提示
在第一组数据中,货币系统(2,[3,10])和给出的货币系统(n,a)等价,并可以验证不存在m<2的等价的货币系统,依次答案为2.
在第二组数据中,可以验证不存在m
对于 100% 的数据,满足 1 ≤ T ≤ 20,1≤n≤ 100,1≤ a[i] ≤ 25000。
代码
- #include
- #include
- using namespace std;
- #define ll long long
- int n,f[50005],t,a[105],maxx,ans;
- int main(){
- cin>>t;
- while(t--){
- cin>>n;
- memset(f,0,sizeof f);
- f[0]=1;
- maxx=0,ans=0;
- for(int i=1;i<=n;i++){
- cin>>a[i];
- maxx=max(a[i],maxx);
- }
- for(int i=1;i<=n;i++){
- for(int j=a[i];j<=maxx;j++){
- f[j]=f[j]+f[j-a[i]];
- }
- }
- for(int i=1;i<=n;i++){
- if(f[a[i]]==1){
- ans++;
- }
- }
- cout<
"\n"; - }
- return 0;
- }
评论记录:
回复评论: