分类目录归档：程序相关

C,Python,环境配置等

邮票面值设计

发表回复

【问题描述】
【描述 Description 】

　　给定一个信封，最多只允许粘贴N张邮票，计算在给定M（N+M<=10）种邮票的情况下（假定所有的邮票数量都足够）,如何设计邮票的面值，能得到最大max ，使得1～max之间的每一个邮资值都能得到。 例如，N=3，M＝2，如果面值分别为1分、4分，则在l分～6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）：如果面值分别为1分、3分，则在1分～7分之间的每一个邮资值都能得到。可以验证当N=3，M＝2时，7分就是可以得到连续的邮资最大值，所以MAX=7，面值分别为l分、3分。 【样例输入】 共一行，两个整数，分表为N与M的值。 【输入格式 Input Format 】 一行，分别为N,M。 【输出格式 Output Format 】 两行。 第一行为m种邮票的面值，按升序排列，各数之间用一个空格隔开。 第二行为最大值。 【样例输入 Sample Input 】 3 2 【样例输出 Sample Output 】 1 3 MAX=7 算法分析 深搜加DP 栈记录所用邮票的面值 每次面值的搜索的范围为：上一次使用的邮票面值+1 to 上一次连续达到的最大值+1 然后DP，记录达到每个面值用的最少邮票数，不断更新最优解 注意要从第1张邮票开始，否则要出错 【代码】 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

#include <stdio.h>
 
int a[11], ans[11];
int b[1001];
int n, m, max;
 
int dp(int i)
{
       int j, k;
 
       for (j = 1; j < 1001; j++)
              b[j] = 9999;
 
       for (j = 1; j <= i; j++)
              b[a[j]] = 1;
       j = 0;
 
       do
       {
              j++;
 
              for (k = 1; k <= i; k++)
                     if (j > a[k] && b[j - a[k]] + 1 < b[j])
                            b[j] = b[j - a[k]] + 1;
 
       }while (b[j] <= m);
       return j;
}
 
void search(int i)
{
       int j, k;
 
       if (i > n)
       {
              if (dp(i - 1) - 1 > max)
              {
                     for (j = 1; j <= 10; j++)
                            ans[j] = a[j];
                     max = dp(i - 1) - 1;
              }
              return;
       }
       j = dp(i - 1);
 
       for (k = j ; k >= a[i - 1] + 1; k--)
       {
              a[i] = k;
              search(i + 1);
       }
}
 
int main()
{
 
       int i;
       scanf("%d%d", &m, &n);
 
       max = 0;
       a[1] = 1;
       search(2);
 
       for (i = 1; i <= n; i++)
              printf("%d ", ans[i]);
 
       printf("\n");
       printf("MAX=%d\n", max);
       return 0;
}

High Performance Web Site(高性能网站)读后感

发表回复

High Performance Web Site读后感

看到五月的程序员杂志上江永源童鞋有对yahoo优化原则的总结：
合并小数据文件到一个请求
拆分大数据文件到多个请求
优化文件内容、压缩、减少不必要的数据传输
缓存可以缓存的数据、文件

以前看过这本书的中文版，也看过别人写的简单版本以及yahoo军规34条，对其中的内容比较熟悉，
这次再看其英文版本，有感如下：

用户访问一个页面，就是将用户所需要的东西从服务器端传输到客户端的过程，那么如何减少这个传输时间呢？
第一：【减少传输的内容】
在不影响效果的情况下减少传输的内容
规则四：Gzip Components Gzip压缩
通过压缩，缩小文件体积，从而达到减少传输内容的目的
规则八：Make JavaScript and CSS External 将JS和CSS外链
将js和css外链，或者说是放在其它域名下，可以提高并发数，利用规则
规则十：Minify JavaScript and CSS 减小JS和CSS的体积
写JS和CSS都是有技巧的，用最少的代码实现同样的功能，减少空白，增强逻辑性，用缩写方式等等
规则十二：Remove Duplicate Scripts 删除重复脚本
规则十三：Configure ETags 设定ETags
规则十四： Make Ajax Cacheable 让Ajax可以缓存

第二：【提高传输速度，减少传输距离，减少其它计算或查找时间】
规则二：Use a Content Delivery Network 利用CDN技术
规则九：Reduce DNS Lookups 减少DNS查找
规则十一：Avoid Redirects 避免重定向

第三：【减少传输的次数】
一般来说，一个页面肯定有多个内容需要从服务器传输到客户端，此时我们需要减少传输的次数
规则一：减少HTTP请求，
就严重强调了其重要性，几种常见的方法：1，合并文件，2、CSS Sprites，3、图象地图，4、内联图像
规则三：Add an Expires 设置头文件过期，
缓存只是在用户非首次访问页面时有用，这也同样减少了传输的内容

第四：【用户体验】(渲染应该会更加贴切一些)
规则五：Put Stylesheets at the Top 把CSS放顶部
让浏览者能尽早的看到网站的完整样式，并且可以利用浏览器的加载效果
规则六：把JS放底部
网站呈现完毕后再进行功能设置，当然这些JS要在你的加载过程中不影响内容表现
规则七：Avoid CSS Expressions 避免CSS Expressions

以上只是以我自己的理解将十四条规则做了一个简单的分类，仅个人看法
另外，觉得书中所说的前端优化是在已有条件的基础上做的一些细节部分的调整，从而提高整体的前端性能
不过对于优化来说，后端的优化还是灰常重要的

over

猫狗大战

发表回复

问题描述
【描述 Description】
　　新一年度的猫狗大战通过SC(星际争霸)这款经典的游戏来较量，野猫和飞狗这对冤家为此已经准备好久了，为了使战争更有难度和戏剧性，双方约定只能选择Terran(人族)并且只能造机枪兵。

　　比赛开始了，很快，野猫已经攒足几队机枪兵，试探性的发动进攻；然而，飞狗的机枪兵个数也已经不少了。野猫和飞狗的兵在飞狗的家门口相遇了，于是，便有一场腥风血雨和阵阵惨叫声。由于是在飞狗的家门口，飞狗的兵补给会很快，野猫看敌不过，决定撤退。这时飞狗的兵力也不足够多，所以没追出来。

　　由于不允许造医生，机枪兵没办法补血。受伤的兵只好忍了。555－
　　现在，野猫又攒足了足够的兵力，决定发起第二次进攻。为了使这次进攻给狗狗造成更大的打击，野猫决定把现有的兵分成两部分，从两路进攻。由于有些兵在第一次战斗中受伤了，为了使两部分的兵实力平均些，分的规则是这样的：1）两部分兵的个数最多只能差一个；2）每部分兵的血值总和必须要尽可能接近。现在请你编写一个程序，给定野猫现在有的兵的个数以及每个兵的血格值，求出野猫按上述规则分成两部分后每部分兵的血值总和。

【输入格式 Input Format】
第一行为一个整数n(1<=n<=200)，表示野猫现在有的机枪兵的个数。以下的n行每行一个整数，表示每个机枪兵的血格(1<=ai<=40)。 【输出格式 Output Format 】 只有一行，包含两个数，即野猫的每部分兵的血值总和，较小的一个值放在前面，两个数用空格分隔。 【样例输入 Sample Input 】 3 35 20 32 【样例输出 Sample Output】 35 52 【算法分析】 1 to n div 2为前一半数，n div 2+1 to n为后一半数之后枚举a[i],a[j]看是否可以交换 代码 方法一： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

#include <stdio.h>
 
int abs(int t)
{
 
       if (t < 0)
              return -t;
       else
              return t;
}
 
int main()
{
 
       int a[201], b[201];
       int n, i, j, l1, l2, sum1 , sum2, temp;
 
       scanf("%d", &n);
 
       l1 = n / 2;
       l2 = n - l1;
       sum1 = 0;
       sum2 = 0;
 
       for (i = 1; i <= l1; i++)
       {
              scanf("%d", &a[i]);
              sum1 += a[i];
       }
 
       for (i = 1; i <= l2; i++)
       {
              scanf("%d", &b[i]);
              sum2 += b[i];
       }
 
       for (i = 1; i <= l1; i++)
       {
              for (j = 1; j <= l2; j++)
              {
                     if (abs((sum1 + b[j] - a[i]) - (sum2 + a[i] - b[j])) < abs(sum1 - sum2))
                     {
                            sum1 = sum1 + b[j] - a[i];
                            sum2 = sum2 + a[i] - b[j];
                            temp = a[i];
                            a[i] = b[j];
                            b[j] = temp;
                     }
              }
       }
 
       if (sum1 < sum2)
              printf("%d %d\n", sum1, sum2);
       else
              printf("%d %d\n", sum2, sum1);
 
       return 0;
}

方法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

Const
maxn=200;
maxm=8000;
Var
f:array[0..maxn,0..maxm] of boolean;
 
n,ans,mid:integer;
d:array[1..maxn] of integer;
 
Procedure Init;
var i:integer;
begin
　　fillchar(f,sizeof(f),false);
　　f[0,0]:=true;
　　ans:=0;
　　readln(n);
　　for i:=1 to n do readln(d[i]);
　　for i:=1 to n do ans:=ans+d[i];
　　mid:=ans div 2;
end;
 
Procedure Work;
var i,j,k:integer;
 
begin
　　for i:=1 to n do
　　  for k:=i downto 1 do
　　　　for j:=mid-d[i] downto 0 do
　　　　  if f[k-1,j] then f[k,j+d[i]]:=true;
end;
 
Procedure Print;
 
var i,j:integer;
begin
　　i:=0;j:=0;
　　while (not f[n div 2,mid+j]) do dec(j);
　　j:=mid+j;
　　writeln(j,' ',ans-j);
end;
 
BEGIN
init;
work;
print;
END.