posts - 99,  comments - 8,  trackbacks - 0
 
hdu 1016 搜索
#include <stdio.h>
#include <stdlib.h>

int n;
static int visited[20];
static int stack[20];
int top;

int prime[38] = {0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1}; 

void dfs (int i,int top)
{
     stack[top] = i;  
    if (top == n - 1)
    {
 
        for (int m = 2; m <= n; m ++)
        {
            if (prime[stack[top] + m] && prime[m + 1] && !visited[m])
            {
                stack[top + 1] = m;
                 //printf ("%d\n",m);
                for (m = 1; m <= n; m ++)
                {
                    printf (m == 1 ? "%d" :" %d", stack[m]);            
                }
                printf ("\n");
            }
        }
    }

    else
    {    
        for (int j = 1; j <= n; j ++)
        {
            if (prime[i + j] && !visited[j])
            {
                visited[j] = 1;
                dfs (j,top+1);
                visited[j] = 0;
            }
        }
    }    
}


int main ()
{
    int cn = 0;
    
    while ( scanf ("%d", &n) != EOF )
    {
        printf ("Case %d:\n",++ cn);
        visited[1] = 1;   top = 1;
        dfs (1,top);
        printf ("\n");
    }
    return 0;
}




posted @ 2010-08-18 14:25 雪黛依梦 阅读(404) | 评论 (0) | 编辑 收藏
hdu 1013 数学题
//这个题目如果用普通的求模求余方法做一定会超时的
//关键是发现数字的规律，当位数之和 > 10 时 其实减去 9 就是位数之和
//采用字符输入便于求和计算，同时处理了大数问题
数组应开的比较大
 1#include <stdio.h>
 2#include <stdlib.h>
 3
 4int main ()
 5{
 6    char s[999];
 7    
 8    int i , sum;
 9    
10    while (scanf ("%s",s) && s[0] != '0')
11    {
12          for (i = sum = 0; s[i]; i ++)
13          {
14              sum += s[i] - '0';
15          }
16          
17          printf ("%d\n", sum%9 == 0 ? 9 : sum %9);
18    }
19    return 0;
20}
21
posted @ 2010-08-16 11:37 雪黛依梦 阅读(155) | 评论 (0) | 编辑 收藏
hdu 1069 DP 猴子取香蕉
//解题思路：每一个立方体必然有 3 个面积，所以 N 种类型的立方体，必然有 3 * N  个面积组合
//将所有的面积从小到大排列之后，每组面积必然对应一个高的值，依据题意，要使高之和最大，所
//以这个问题就转化成了求最长子列和的最大值
  1#include <stdio.h>
  2#include <stdlib.h>
  3#include <string.h>
  4
  5//定义一个结构体存立方体的面积 和  边长
  6struct cube
  7{
  8       int x;
  9       int y;
 10       int z;
 11       int area;
 12}b[200];    //结构体变量 
 13    
 14//这是调用qsort 函数时必须要用的 
 15int compare(const void* a,const void* b)
 16{
 17    return (*(cube *)a).area-(*(cube *)b).area;   //如果 < 则返回负数  如果 = 则返回0  如果 > 则返回 1 
 18}
 19    
 20// 判断上面的两条边都要 < 下面的两条边
 21int com (cube a, cube b)
 22{
 23    if ( (a.x < b.x && a.y < b.y) || (a.y < b.x && a.x < b.y) )   如：10      20       与  40      50
 24       return 1;
 25       
 26       else
 27       return 0;
 28} 
 29 
 30int main ()
 31{
 32    int sum[200];
 33    
 34    //用来控制下标的
 35    int dir[3][3] = { {0, 1, 2}, {0, 2, 1}, {1, 2, 0} };    
 36    
 37    int n;
 38    int a[3];
 39    int count = 0;
 40    while (scanf ("%d", &n))
 41    {
 42          if (!n)
 43          break; 
 44          int num = 0;
 45          memset (sum, 0, sizeof (sum));
 46          for (int i = 0; i < n; i ++)
 47          {
 48              scanf ("%d%d%d", &a[0], &a[1], &a[2]);  //读入输入的三个数据 
 49          
 50              for (int j = 0; j < 3; j ++)  //将所有可能的 立方体构成 存入到数组 b 中 
 51              {
 52                     b[num].x = a[ dir[j][0] ];
 53                     b[num].y = a[ dir[j][1] ]; 
 54                     b[num].z = a[ dir[j][2] ];
 55                     b[num].area = b[num].x * b[num].y;     
 56                     num ++;    //错点          
 57              }
 58                  
 59          }
 60          
 61          //对 b 数组按面积进行快速排序
 62          qsort (b, n * 3, sizeof (b[0]), compare); 
 63          
 64          /*
 65          测试排序是否正确
 66          for (int i = 0; i < 3 * n; i ++)
 67          {
 68              printf ("%d\t%d\t%d\t%d\n",b[i].x, b[i].y, b[i].z, b[i].area);
 69          }*/
 70          
 71          //在满足题目条件：上面的两条边都要 < 下面的两条边的情况下找到最大的高的和
 72          sum[0] = b[0].z;
 73          for (int i = 1; i < 3 * n; i++)
 74          {
 75              int temp = 0;
 76              for (int j = 0; j < i; j ++)
 77              {
 78                  if ( sum[j] > temp && ( com(b[j],b[i]) ) ) //要比较的高的值  满足题目的条件 累加求和 
 79                  {
 80                       temp = sum[j]; 
 81                  }
 82              }    
 83              sum[i] = temp + b[i].z;
 84              
 85              //printf ("%d\t",sum[i]);
 86          } 
 87          
 88          //printf ("\n");
 89          
 90          //输出高的和
 91          int max = -1;
 92          for (int i = 0; i < 3 * n; i ++)
 93          {
 94              if (max < sum[i])
 95                 max = sum[i];
 96          } 
 97          
 98          printf ("Case %d: maximum height = %d\n", ++count , max);
 99                  
100    }
101    
102    return 0; 
103}
104

posted @ 2010-08-16 10:03 雪黛依梦 阅读(702) | 评论 (0) | 编辑 收藏
hdu 2059 DP 龟兔赛跑
DP 问题的关键在于：如何分解子问题以及求得子问题的最优解
 //这题可以看成0,1...n,n+1一共n+2个终点站包括起始点,分别求出到达每个站的最短时间即可
//第 i  站时用前面的timeT[i - 1] + 后面的可能解，由于timeT保存的是到该站时的最短时间，所以不断递归 i  之至 n 就可以求得最优解
  //dp[i]=dp[i-1]+f(i-1,i)(即i-1,到i的最短时间)
#include <stdio.h>
#include <stdlib.h>
int main ()
{
    int L;
    int N, C, T;
    int vr, vt1, vt2;
    int p[103];         //记录各站p[i]到起点的距离 
    double timeT[103];     //记录第i段的最短时间 
    double timeR;
    
    while ( scanf ("%d",&L) != EOF )
    {
          scanf ("%d%d%d", &N , &C, &T);
          scanf ("%d%d%d", &vr, &vt1, &vt2);
          
          //兔子的时间         
          timeR = L * 1.0 / vr;
 
          //记录各站p[i]到起点的距离
          p[0] = 0;
          p[N + 1] = L;
          for (int i = 1; i <= N; i ++)
          {
              scanf ("%d", &p[i]);
          }
          
          //找到p[i] 到 p[i + 1]段的最短耗时
          timeT[0] = 0;  //递归出口 
          
          double len;
          double e, min;
          for (int i = 1; i <= N + 1; i ++)
          {
               min = 9999999.9;
              
              for (int j = 0; j < i; j ++)
              {
                  len = p[i] - p[j];
                  
                  if (len > C)
                     e = ( 1.0 * C / vt1 ) + (len - C + 0.0) * 1.0 / vt2 ;
                     else
                     e = len * 1.0 / vt1  ;
                  
                  e += timeT[j];
                  if (j)
                  e += T;
                  
                  if ( e < min)
                  min = e;   
              }
              timeT[i] = min;
          }
           
          
          if (timeT[N + 1] < timeR)
          {
                  printf ("What a pity rabbit!\n");
          }
          else 
          printf ("Good job,rabbit!\n");
    }
    
    return 0;

}
posted @ 2010-08-15 16:16 雪黛依梦 阅读(252) | 评论 (0) | 编辑 收藏
hdu 1466 DP 直线的可能交点数目
//思路：分析易知递推关系式：dp[i][j] = （i - r）* r + dp[r][k]     //  r条自由线和i - r条平行线的交点数 +   r条直线本身的交点数
//        dp[i][j]表示 i 条直线可能的交点种数 j = (i - r）* r + dp[r][k]
//        r表示自由线的条数，（i - r）表示平行线的条数，（i - r）* r 表示平行线和自由线的交点个数
//        r 可以取 0 -- i - 1 但是这里初始化的缘故循环时 r 取 1 -- i - 1
//        dp[r][k]表示 r 条直线本身的交点个数
//        max i 条直线最多的交点数
//        先把i条直线0个交点的情况初始值为1(这是一定的)，然后若i-r条直线有j个交点则i条直线必有（i-r）*r+j个交点，标记为 1 
//        通过标记为 1 的下标 j  为 n 取 i 时的交点数 
本题的巧妙之处在于：将下标对应为交点种类输出，同时又满足了从小到大输出这个条件

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main ()
{
    int dp[21][191];
    
    memset (dp, 0 , sizeof (dp));
    
    for (int i = 0; i < 21; i ++)
    {
        for (int j = 0; j < 191; j ++)
        {
            dp[i][0] = 1;          //0个交点的情况初始值为1
        }
    } 
    
    dp[1][0] = 1;      //递归出口 
    
    for (int i = 2; i < 21; i ++)
    {
        for (int r = 1; r < i; r ++)
        {
            for (int j = 0; j < 191; j ++)  //20条直线最多交点数为 190  
            {
                if (dp[i - r][j] == 1)  //递归思想：如果 r 条直线存在交点数 j (这里 i - r 保证了r 可以取到 1 至 i - 1，即有dp[r][k])
                dp[i][j + (i - r) * r] = 1;  //则i条直线必有（i-r）*r+j(j 即dp[r][k])个交点，标记为 1 
            }
        }
    } 
    
    
    int n;
    while (scanf ("%d", &n) != EOF)
    {
          printf ("%d",0);
          int max = n * (n - 1) / 2;
          for (int j = 1; j <= max; j++)
          {
              if (dp[n][j])
              printf (" %d",j);
          }
          printf ("\n");
    } 
    
    return 0; 
}
posted @ 2010-08-15 10:02 雪黛依梦 阅读(454) | 评论 (0) | 编辑 收藏
hdu 1087 DP
//本题是在 grids 2757的基础上得到解决的，即找到最大子例的和
// sum[i]   用于存放到 i 位置为止的子序列的和,所以只需要找到前i - 1 中的sum 所存的最大值再加上本身就可以了

#include <stdio.h>
#include <stdlib.h>

int main ()
{
    int b[1001];
    int n;
    __int64 sum[1001];  //用于存放到 i 位置为止 的子序列的和 
    
    while (scanf ("%d", &n) && n)
    {
          
          for ( int i = 0; i < n;i ++)
          {
              scanf ("%d", &b[i]);
          }
          
          sum[0] = b[0];   
          for (int i = 1; i < n; i ++)               //下面的处理和 grids      2757的处理思想是一样的，只不过sum  数组存的是和值
          {
              int tempMaxsum = 0;
              for (int j = 0; j < i; j ++)     //因为 i 之前的和值已经存储在了sum中，
                                               // 所以只需要找到最大的tempMaxSum后再加上 i 位置本身的值就可以了 
              {
                  if (b[j] <b[i] && tempMaxsum < sum[j])
                  {
                           tempMaxsum = sum[j];   
                  }
              }
              
              sum[i] = tempMaxsum + b[i];
              
          }
          
          __int64 max = -1;
          for (int i = 0; i < n; i ++)
          {
              if (max < sum[i])
              {
                      max = sum[i];
              }
              
          } 
          printf ("%I64d\n",max);
          
    }
    
    return 0;
}
posted @ 2010-08-14 21:35 雪黛依梦 阅读(762) | 评论 (0) | 编辑 收藏
grids 2757 求最大子例长度
//动态规划题目最重要的一点是如何将问题分解得到子问题，并且将子问题解决
//本题以下标为状态量，找到以该下标位置 i 为终点时的最长子列：如果 i 位置的值 > i - 1位置的值，则长度加 1 ，
//所以利用判断大小来递归，出口是：下表为 0 时，长度为 1
//利用 nMaxLen【i】记录长度避免了重复计算

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main ()
{
    int n;
    int b[1000];
    int nMaxLen[1000];
    while (scanf ("%d", &n) != EOF && 1 <= n && n <= 1000)
    {
          memset (nMaxLen, 0 ,sizeof(nMaxLen));
          //将输入的数值存入数组 b 中 
          for (int i = 0; i < n; i ++)
          {
              scanf ("%d", &b[i]);
          }
          
          //找到每一个状态下标 i 对应的最大子列长度，并将其存入数组nMaxLen[]中
          nMaxLen[0] = 1;
          for (int i = 1; i < n; i ++)   
          {
              int temp = 0;
              for (int j = 0; j < i ; j ++)
              {
                  if ( b[i] > b[j])
                  {
                       if (temp < nMaxLen[j])          //只有当当前的长度 <  之前一位数的序列长时才可以赋值，最后起到 temp + 1 的作用     
                                                                                            // 为什么:最大序列可能出现在 j 之后如： 7    9    10     6     11
                       temp = nMaxLen[j];
                  }
              }
              nMaxLen[i] = temp + 1;
          }
          
          //遍历数组nMaxLen从中读出最大值，即：在该位置时取得最大的子序列
          int max = -1;
          for (int i = 0; i < n; i ++)
          {
              if (nMaxLen[i] > max)
              max = nMaxLen[i];
          } 
          
          printf ("%d\n", max);
    }
    //system ("pause");
    return 0;
}
posted @ 2010-08-14 15:38 雪黛依梦 阅读(180) | 评论 (0) | 编辑 收藏
hdu 1480 递归 钥匙问题 二

/*解题思路和1297类似：都是通过递推第 n --- 1 种情况合法与不合法，从而知道第 n  种
如下：

设lock[i]表示：有 i个槽的钥匙的个数
设one[i]表示：有 i个槽且左边第一个槽深度为1的钥匙的个数
设two[i]表示：有 i个槽且左边第一个槽深度为2的钥匙的个数
..
..
设six[i]表示：有 i个槽且左边第一个槽深度为6的钥匙的个数

则显然：lock[i]=one[i]+two[i]+ three[i]+four[i]+five[i]+six[i]

由于易知：one[i]=six[i],two[i]=three[i]=four[i]=five[i]

则可以得到：lock[i]=one[i]*2+two[i]*4


当左边第一个凿深是1  或  2 时  与后面的 i - 1 种不合法的情况结合必须构成合法的，由此递推开来
其中：
 
one[i]=one[i-1]+two[i-1]+three[i-1]+four[i-1]+five[i-1]+a[i]; //可理解为所有LOKE（i-1）前加1,
                                                              所以后面的不能出现six【i - 1】，否则1  6相邻
      =one[i-1]+two[i-1]*4 +a[i] //而a[i]即为不成立的LOKE(i-1)，b[i]同理
     
two[i]=one[i-1]*2+two[i-1]*4 +b[i]

其中，a[i] 和b[i]的含义分别是：
a[i]表示“有 i个槽且左边第一个槽深度为1，同时这种钥匙在除掉第一个槽后不再是钥匙”的钥匙的个数。
例如 123,124,125,134,135,145,126,136,146,156 就属于这种情况。

b[i]表示“有 i个槽且左边第一个槽深度为2，同时这种钥匙在除掉第一个槽后不再是钥匙” 的钥匙的个数。

分析到这里，可以知道，关键的是求a[i]和b[i]，我们可以得到如下表达式：
a[i]=(2^(i-1)-2)*6+(2^(i-2)-1)*4
b[i]=(2^(i-1)-2)*9

其中，a[i] 的各部分的含义如下：
(2^(i-1)-2)*6：
当去掉第一位，后面i-1位只有 (2,3)或者 (2,4) 或者(2,5) 或者(3,4) 或者(3,5) 或者(4,5)两种数字的时候，
显然是不合法的钥匙（不满足至少有3个不同的深度），加上第一位的1则显然是一个合格的钥匙。所以后面的数
字可以为一个组合中两个数字的任意一个，根据乘法原理i-1位一共有2^(i-1)种组合，当然还需要去掉两种特殊
情况，就是后面i-1位完全相同的情况。满足这种条件的一共有上面六种组合，所以得到(2^(i-1)-2)*6。
(2^(i-2)-1)*4：
当去掉第一位，后面i-1位只有 (2,6)或者 (3,6) 或者(4,6) 或者(5，6)两种数字的时候，显然是不合法的钥匙
（不满足至少有3个不同的深度），加上第一位的1则“可能”是一个合格的钥匙。因为要注意满足“相连的槽其
深度之差不得为5”这个条件，所以，紧跟着1的绝对不能是6，这样，相对于上面的分析，后面i-2位可以是每组
中的任意一个，所以有2^(i-2)，还要减去1是因为同样要排除后面全部是和第2位一样的数字这样的情况。满足
这种条件的一共有上面的四种组合，所以得到(2^(i-2)-1)*4。

b[i] 的含义如下：
(2^(i-1)-2)*9：
当去掉第一位，后面i-1位只有 (1,3)或者 (1,4) 或者(1,5) 或者(3,4) 或者(3,5) 或者(3,6) 或者(4,5) 或者(4,6)
 或者(5,6) 两种数字的时候，显然是不合法的钥匙（不满足至少有3个不同的深度），加上第一位的1则显然是一个合
 格的钥匙。所以后面的数字可以为一个组合中两个数字的任意一个，根据乘法原理i-1位一共有2^(i-1)种组合，当然
 还需要去掉两种特殊情况，就是后面i-1位完全相同的情况。满足这种条件的一共有上面9种组合，所以得到(2^(i-1)-2)*9。
 （排除(1,6)是因为这样的不合法情况和前面的第一个凿 2 相结合后组成的钥匙还是不合法的）
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

__int64 Lock[26];   //凿深为 i 时的可能钥匙种类 
__int64 one[26];    //当左边第一个凿深为 1 时的可能钥匙种类 
__int64 two[26];    //当左边第一个凿深为 2 时的可能钥匙种类
__int64 a[26];      //当左边第一个凿深为 1 时,后面的 i - 1 中可能的不合法情况
__int64 b[26];      //当左边第一个凿深为 1 时,后面的 i - 1 中可能的不合法情况

int main ()
{
    one[3] = 16;
    two[3] = 18;
    Lock[3] = 104;   
    for (int i = 4; i < 26; i ++)
    {

        a[i] = 16 * (pow (2, i - 2) - 1);
        b[i] = 9 * (pow (2, i - 1) - 2);
        
        one[i] = one[i - 1] + 4 * two[i - 1] + a[i];
        two[i] = 2*one[i - 1] + 4 * two[i - 1] + b[i];
        
        Lock[i] = 2 * one[i] + 4 * two[i];
    }
    
    for (int i = 3;i < 26; i ++)
    {
        printf("N=%d: %I64d\n", i, Lock[i]);
    }
    system ("pause");
    return 0;
} 
posted @ 2010-08-14 14:01 雪黛依梦 阅读(219) | 评论 (0) | 编辑 收藏
grids 2760 简单的动规题

//利用aMaxSum来标记该位置坐标上的值是否被计算过了，如果被计算了直接利用原来已经存在aMaxSum中的值
//递归是一个比较难以理解的知识，最好的方法是自己通过画出递归调用图来理解中间的过程
//动态规划是以递归为基础的，需要解决的是将递归中出现的重复子问题记录下来，以减少下次递归时的重复计算从而减少时间复杂度；

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int a[101][101];
int n;

int aMaxSum[101][101];  


int max_sum (int r,int j)
{ 
   
    if ( r == n - 1)
    return a[r][j];
    
    if (aMaxSum[r + 1][j] == -1)
    aMaxSum[r + 1][j] = max_sum (r + 1, j);
    
    if (aMaxSum[r + 1][j + 1] == -1)
    aMaxSum[r + 1][j + 1] = max_sum (r + 1, j + 1);
    
    if ( aMaxSum[r + 1][j] > aMaxSum[r + 1][j + 1])
       return aMaxSum[r + 1][j] + a[r][j];
       
       else
       return aMaxSum[r + 1][j + 1] + a[r][j];  
}

int main ()
{
    while ( scanf ("%d", &n) != EOF )
    {
          for (int i = 0; i < n; i ++)
          {
              for (int j = 0; j < i+ 1; j ++ )
              {
                  scanf ("%d", &a[i][j]);
              }
          }
          memset (aMaxSum, -1, sizeof (aMaxSum));
          int max = max_sum (0,0);
          
          printf ("%d\n", max);
    }
    
    return 0;
}

posted @ 2010-08-14 10:54 雪黛依梦 阅读(117) | 评论 (0) | 编辑 收藏
//hdu 2044

#include <stdio.h>
#include <stdlib.h>
int main ()
{ 
    __int64 mi[50];
    
    mi[0]=0;
    mi[1] = 1;
    mi[2] = 2;
    for (int i = 3; i < 50; i ++)
    {
        mi[i] = mi[i - 2] + mi[i - 1];
    } 
    
    int n;
    int a, b;
    
    while ( scanf ("%d", &n) != EOF )
    {
          for (int i = 0; i < n; i ++)
          {
              scanf ("%d%d", &a, &b);
              
              printf ("%I64d\n",a < b ? mi[b - a]: 0);
          }
    }
    
     return 0;
}
//关键是弄清楚问题的本质：因为达到  b 是有两条路径的  由此递推
posted @ 2010-08-13 21:31 雪黛依梦 阅读(213) | 评论 (0) | 编辑 收藏
仅列出标题
共10页: First 2 3 4 5 6 7 8 9 10 
Copyright ©2024 雪黛依梦 Powered By: 博客园 模板提供：沪江博客
<2024年5月>
日一二三四五六
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

常用链接

留言簿(4)

随笔分类

随笔档案

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜