华师一附中OI组

标题: 刘伟杰李香来程序大楼 [打印本页]

---

作者: admin    时间: 2018-10-16 19:03
标题: 刘伟杰李香来程序大楼
这是刘，李两位同学的程序暂存大楼，他们的程序写在这里，自己欣赏

---

作者: 刘伟杰    时间: 2018-10-16 21:04


luogu p1095 守望者的逃离 水题

思路：dp+贪心

AC代码：

1. #include <bits/stdc++.h>
   
2. 
   
3. using namespace std;
   
4. 
   
5. int dp[15000000];
   
6. int m,s,t;
   
7. 
   
8. 
   
9. int main()
   
10. {
    
11.    scanf("%d%d%d",&m,&s,&t);
    
12.    int i;
    
13.    for(i = 1;i <= t;i++)
    
14.    {
    
15.        if(m >= 10)
    
16.        {
    
17.            m -= 10;
    
18.            dp[i] = dp[i-1] + 60;
    
19.        }else
    
20.        {
    
21.            m+=4;
    
22.            dp[i] = dp[i-1];
    
23.        }
    
24.    }
    
25.    for(i = 1;i <= t;i++)
    
26.    {
    
27.        dp[i] = max(dp[i-1]+17,dp[i]);
    
28.        if(dp[i] >= s)
    
29.        {
    
30.            printf("Yes\n%d",i);
    
31.            return 0;
    
32.        }
    
33.    }
    
34.    printf("No\n%d",dp[t]);
    
35. 
    
36.     return 0;
    
37. }
    

复制代码

---

作者: 刘伟杰    时间: 2018-10-16 21:06
luogu p1098 字符串展开 模拟

特判比较多

AC代码

1. #include <bits/stdc++.h>
   
2. 
   
3. using namespace std;
   
4. 
   
5. char a[100000];
   
6. int p1,p2,p3;
   
7. char bg;
   
8. char ed;
   
9. int main()
   
10. {
    
11. 
    
12.     scanf("%d%d%d",&p1,&p2,&p3);
    
13.     scanf("%s",a);
    
14.     int len = strlen(a);
    
15.     for(int i = 0;i < len;i++)
    
16.     {
    
17.         if(a[i] != '-')
    
18.         {
    
19.             printf("%c",a[i]);
    
20.         }else
    
21.         {
    
22.             if(a[i-1] == '-')
    
23.             {
    
24.                 printf("-");
    
25.                 continue;
    
26.             }
    
27.             if(a[i-1] >= a[i+1])
    
28.             {
    
29.                 printf("-");
    
30.                 continue;
    
31.             }
    
32.             if(a[i+1] - a[i-1]> 27)
    
33.             {
    
34.                 printf("-");
    
35.                 continue;
    
36.             }
    
37.             if(a[i+1] - a[i-1] == 1)  continue;
    
38.             if(p1 == 1)
    
39.             {
    
40.                 if(p3 == 2)
    
41.                 {
    
42.                    ed = a[i-1] + 1;
    
43.                    bg = a[i+1] - 1;
    
44.                    for(int j = bg;j >= ed;j--)
    
45.                    {
    
46.                        char z = j;
    
47.                        for(int k = 1;k <= p2;k++)
    
48.                        {
    
49.                            printf("%c",z);
    
50.                        }
    
51.                    }
    
52.                 }else
    
53.                 {
    
54.                    bg = a[i-1] + 1;
    
55.                    ed = a[i+1] - 1;
    
56.                    for(int j = bg;j <= ed;j++)
    
57.                    {
    
58.                        char z = j;
    
59.                        for(int k = 1;k <= p2;k++)
    
60.                        {
    
61.                            printf("%c",z);
    
62.                        }
    
63.                    }
    
64.                 }
    
65.             }
    
66.             if(p1 == 3)
    
67.             {
    
68.                 if(p3 == 2)
    
69.                 {
    
70.                    ed = a[i-1] + 1;
    
71.                    bg = a[i+1] - 1;
    
72.                    for(int j = bg;j >= ed;j--)
    
73.                    {
    
74.                        for(int k = 1;k <= p2;k++)
    
75.                        {
    
76.                            printf("*");
    
77.                        }
    
78.                    }
    
79.                 }else
    
80.                 {
    
81.                    bg = a[i-1] + 1;
    
82.                    ed = a[i+1] - 1;
    
83.                    for(int j = bg;j <= ed;j++)
    
84.                    {
    
85.                        for(int k = 1;k <= p2;k++)
    
86.                        {
    
87.                            printf("*");
    
88.                        }
    
89.                    }
    
90.                 }
    
91.             }
    
92.             if(p1 == 2)
    
93.             {
    
94.                 if(p3 == 2)
    
95.                 {
    
96.                    ed = a[i-1] + 1;
    
97.                    bg = a[i+1] - 1;
    
98.                    for(int j = bg;j >= ed;j--)
    
99.                    {
    
100.                        char z = j;
     
101.                        if(z > 96)
     
102.                        {
     
103.                            z = z - 32;
     
104.                        }
     
105.                        for(int k = 1;k <= p2;k++)
     
106.                        {
     
107.                            printf("%c",z);
     
108.                        }
     
109.                    }
     
110.                 }else
     
111.                 {
     
112.                    bg = a[i-1] + 1;
     
113.                    ed = a[i+1] - 1;
     
114.                    for(int j = bg;j <= ed;j++)
     
115.                    {
     
116.                        char z = j;
     
117.                        if(z > 96)
     
118.                        {
     
119.                            z = z - 32;
     
120.                        }
     
121.                        for(int k = 1;k <= p2;k++)
     
122.                        {
     
123.                            printf("%c",z);
     
124.                        }
     
125.                    }
     
126.                 }
     
127.             }
     
128.         }
     
129.     }
     
130. 
     
131.     return 0;
     
132. }
     

复制代码

---

作者: 刘伟杰    时间: 2018-10-16 21:19
luogu UVA253 cube painting
穷举 可以用到数学思想：不管骰子怎么转动，相对的两面不变。

穷举AC代码：

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. int dir[6][6] = { { 0, 1, 2, 3, 4, 5 }, { 1, 0, 3, 2, 5, 4 }, { 2, 0, 1, 4, 5, 3 }, { 3, 0, 4, 1, 5, 2 }, { 4, 0, 2, 3, 5, 1 }, { 5, 1, 3, 2, 4, 0 } };
   
4. char a[10],b[10],s[20];
   
5. bool judge()
   
6. {
   
7.     for (int i=0; i<6; i++)
   
8.     {
   
9.         char temp[10]="";
   
10.         for (int j=0; j<6; j++)
    
11.             temp[j]=a[dir[i][j]];
    
12.         for (int j=0; j<4; j++)
    
13.         {
    
14.             char c_temp;
    
15.             c_temp=temp[1];
    
16.             temp[1]=temp[2];
    
17.             temp[2]=temp[4];
    
18.             temp[4]=temp[3];
    
19.             temp[3]=c_temp;
    
20.             if (strcmp(temp,b)==0) return true;
    
21.         }
    
22.     }
    
23.     return false;
    
24. }
    
25. int main()
    
26. {
    
27.     while (scanf("%s",s)!=EOF)
    
28.     {
    
29.         for (int i=0; i<6; i++)
    
30.             a[i]=s[i];
    
31.         a[6]=0;
    
32.         for (int i=0; i<6; i++)
    
33.             b[i]=s[i+6];
    
34.         b[6]=0;
    
35.         if (judge()) printf("TRUE\n");
    
36.         else printf("FALSE\n");
    
37.     }
    
38. }
    

复制代码

---

作者: 刘伟杰    时间: 2018-10-16 21:26
luogu p1598 垂直柱状图   
过水，注意输出
模拟
AC代码：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. string k[10];
   
4. int m;
   
5. int len[5];
   
6. int counts[27];
   
7. int ans;
   
8. void f(int x)
   
9. {
   
10.     int i;
    
11.     for(i = 0; i < len[x]; i++)
    
12.     {
    
13.         if(k[x][i] == 'A') counts[1]++;
    
14.         if(k[x][i] == 'B') counts[2]++;
    
15.         if(k[x][i] == 'C') counts[3]++;
    
16.         if(k[x][i] == 'D') counts[4]++;
    
17.         if(k[x][i] == 'E') counts[5]++;
    
18.         if(k[x][i] == 'F') counts[6]++;
    
19.         if(k[x][i] == 'G') counts[7]++;
    
20.         if(k[x][i] == 'H') counts[8]++;
    
21.         if(k[x][i] == 'I') counts[9]++;
    
22.         if(k[x][i] == 'J') counts[10]++;
    
23.         if(k[x][i] == 'K') counts[11]++;
    
24.         if(k[x][i] == 'L') counts[12]++;
    
25.         if(k[x][i] == 'M') counts[13]++;
    
26.         if(k[x][i] == 'N') counts[14]++;
    
27.         if(k[x][i] == 'O') counts[15]++;
    
28.         if(k[x][i] == 'P') counts[16]++;
    
29.         if(k[x][i] == 'Q') counts[17]++;
    
30.         if(k[x][i] == 'R') counts[18]++;
    
31.         if(k[x][i] == 'S') counts[19]++;
    
32.         if(k[x][i] == 'T') counts[20]++;
    
33.         if(k[x][i] == 'U') counts[21]++;
    
34.         if(k[x][i] == 'V') counts[22]++;
    
35.         if(k[x][i] == 'W') counts[23]++;
    
36.         if(k[x][i] == 'X') counts[24]++;
    
37.         if(k[x][i] == 'Y') counts[25]++;
    
38.         if(k[x][i] == 'Z') counts[26]++;
    
39. 
    
40.     }
    
41. }
    
42. 
    
43. int main()
    
44. {
    
45.     for(int i = 1; i <= 4; i++)
    
46.     {
    
47.         getline(cin,k[i]);
    
48.         len[i] = k[i].size();
    
49.     }
    
50.     for(int i = 1; i <= 4; i++)
    
51.     {
    
52.         f(i);
    
53.     }
    
54.     for(int i = 1; i <= 26; i++)
    
55.     {
    
56.         ans = max(ans,counts[i]);
    
57.     }
    
58.     m = ans;
    
59.     for(int i = 1; i <= ans; i++)
    
60.     {
    
61.         for(int j = 1; j <= 26; j++)
    
62.         {
    
63.             if(counts[j] >= m)
    
64.             {
    
65.                 printf("* ");
    
66.             }
    
67.             else
    
68.             {
    
69.                 printf("  ");
    
70.             }
    
71.         }
    
72.         m--;
    
73.         printf("\n");
    
74.     }
    
75.     printf("A B C D E F G H I J K L M N O P Q R S T U V W X Y Z");
    
76. 
    
77. 
    
78.     return 0;
    
79. }
    

复制代码

---

作者: admin    时间: 2018-10-17 09:51
楼上的此题函数f应该用数组直接跳转

---

作者: 刘伟杰    时间: 2018-10-17 18:55
luogu P1691 有重复元素的排列问题
我绝对不会说我是用stl的

下面附上AC代码：

1. #include <bits/stdc++.h>
   
2. 
   
3. using namespace std;
   
4. 
   
5. char s1[1000];
   
6. char s2[1000];
   
7. int ans;
   
8. int main()
   
9. {
   
10.     int n;
    
11.     scanf("%d",&n);
    
12.     scanf("%s",s1);
    
13.     sort(s1,s1+n);
    
14.     do{
    
15.         for(int i = 0;i < n;i++)
    
16.         {
    
17.             printf("%c",s1[i]);
    
18.         }
    
19.         ans++;
    
20.         printf("\n");
    
21.     }while(next_permutation(s1,s1+n));
    
22.     printf("%d",ans);
    
23.     return 0;
    
24. }
    

复制代码

---

作者: 刘伟杰    时间: 2018-10-17 19:14


luogu P1706 全排列问题

其实我是特别想用stl的

方法：裸dfs就ok

附上AC代码：

1. #include <bits/stdc++.h>
   
2. 
   
3. using namespace std;
   
4. 
   
5. int a[100];
   
6. int book[100];
   
7. int n;
   
8. void print()
   
9. {
   
10.     for(int i = 1;i <= n;i++)
    
11.     {
    
12.         printf("%5d",a[i]);
    
13.     }
    
14.     printf("\n");
    
15. }
    
16. void dfs(int x)
    
17. {
    
18.     if(x == n+1)
    
19.     {
    
20.         print();
    
21.         return;
    
22.     }
    
23.     for(int i = 1;i <= n;i++)
    
24.     {
    
25.         if(book[i] == 0)
    
26.         {
    
27.             book[i] = 1;
    
28.             a[x] = i;
    
29.             dfs(x+1);
    
30.             book[i] = 0;
    
31.         }
    
32.     }
    
33. }
    
34. 
    
35. 
    
36. int main()
    
37. {
    
38.     scanf("%d",&n);
    
39.     dfs(1);
    
40.     return 0;
    
41. }

复制代码

---

作者: 刘伟杰    时间: 2018-10-17 19:15


luogu P1157 组合的输出

这跟全排列有区别吗。。。有一点吧

裸dfs

AC代码：

1. #include <bits/stdc++.h>
   
2. 
   
3. using namespace std;
   
4. 
   
5. int a[100];
   
6. int book[100];
   
7. int n;
   
8. int k;
   
9. int c;
   
10. void print()
    
11. {
    
12.     for(int i = 1;i <= k;i++)
    
13.     {
    
14.         printf("%3d",a[i]);
    
15.     }
    
16.     printf("\n");
    
17. }
    
18. void dfs(int x)
    
19. {
    
20.     if(x == k+1)
    
21.     {
    
22.         print();
    
23.         return;
    
24.     }
    
25. 
    
26.     for(int i = a[x-1];i <= n;i++)
    
27.     {
    
28.         if(book[i] == 0)
    
29.         {
    
30.             book[i] = 1;
    
31.             a[x] = i;
    
32.             dfs(x+1);
    
33.             book[i] = 0;
    
34.         }
    
35.     }
    
36. }
    
37. 
    
38. 
    
39. int main()
    
40. {
    
41.     scanf("%d%d",&n,&k);
    
42.     a[0] = 1;
    
43.     dfs(1);
    
44.     return 0;
    
45. }

复制代码

---

作者: 刘伟杰    时间: 2018-10-17 19:17

刘伟杰 发表于 2018-10-17 18:55
luogu P1691 有重复元素的排列问题
我绝对不会说我是用stl的

其实应该用搜索的，我错了

---

作者: admin    时间: 2018-10-18 11:53

刘伟杰 发表于 2018-10-17 19:17
其实应该用搜索的，我错了

这个很有用，也需要掌握！

---

作者: 刘伟杰    时间: 2018-10-19 19:10
luogu P1036 选数

一个质数判断加一个裸dfs即可

AC代码：

1. #include <bits/stdc++.h>
   
2. 
   
3. using namespace std;
   
4. int n;
   
5. int s[10000];
   
6. int k;
   
7. int ans;
   
8. 
   
9. bool judge(int x)
   
10. {
    
11.     if(x == 1 || x == 0) return false;
    
12.     if(x == 2) return true;
    
13. 
    
14.     for(int i = 2;i <= x/2;i++)
    
15.     {
    
16.         if(x % i == 0) return false;
    
17.     }
    
18.     return true;
    
19. }
    
20. 
    
21. void dfs(int step,int cnt,int sum)
    
22. {
    
23.     if(step == n+1 || cnt == k)
    
24.     {
    
25.         if(cnt == k && judge(sum)) ans++;
    
26.         return;
    
27.     }
    
28.     dfs(step+1,cnt+1,sum+s[step]);
    
29.     dfs(step+1,cnt,sum);
    
30.     return;
    
31. }
    
32. 
    
33. 
    
34. int main()
    
35. {
    
36.     scanf("%d%d",&n,&k);
    
37.     for(int i = 1;i <= n;i++) scanf("%d",&s[i]);
    
38.     dfs(1,0,0);
    
39.     printf("%d",ans);
    
40.     return 0;
    
41. }
    

复制代码

---

作者: 刘伟杰    时间: 2018-10-19 19:13
luogu P1123

取数游戏（差点做成网络流24。。）

因为周围8个不能取，所以从第一排第一列开始搜，剪枝只用判断左边和上边就ok，也是裸搜加一点点技巧

不知为何输出卡了半天。。

AC代码：

1. #include <bits/stdc++.h>
   
2. 
   
3. using namespace std;
   
4. 
   
5. int n,m,t;
   
6. int maps[1000][1000];
   
7. int book[1000][1000];
   
8. int s[1000];
   
9. int ans = 0;
   
10. 
    
11. void dfs(int sum,int x,int y)
    
12. {
    
13.     if(x > n)
    
14.     {
    
15.        ans = max(ans,sum);
    
16.        return;
    
17.     }
    
18.     int tx = x;
    
19.     int ty = y+1;
    
20.     if(ty > m)
    
21.     {
    
22.         tx++;
    
23.         ty = 1;
    
24.     }
    
25.     if(!book[x-1][y+1] && !book[x-1][y-1] && !book[x][y-1] && !book[x-1][y])
    
26.     {
    
27.         book[x][y] = 1;
    
28.         dfs(sum+maps[x][y],tx,ty);
    
29.         book[x][y] = 0;
    
30.     }
    
31.     dfs(sum,tx,ty);
    
32. 
    
33. }
    
34. 
    
35. 
    
36. int main()
    
37. {
    
38.     scanf("%d",&t);
    
39.     while(t--)
    
40.     {
    
41.         ans = 0;
    
42.         scanf("%d%d",&n,&m);
    
43.         for(int i = 1;i <= n;i++)
    
44.         {
    
45.             for(int j = 1;j <= m;j++)
    
46.             {
    
47.                 scanf("%d",&maps[i][j]);
    
48.             }
    
49.         }
    
50.         dfs(0,1,0);
    
51.         printf("%d\n",ans);
    
52.     }
    
53.     return 0;
    
54. }
    

复制代码

---

作者: 刘伟杰    时间: 2018-10-19 19:17
luogu P1443 马的遍历

普及广搜

其实这题广搜确实比深搜简单，于是就广搜做了。。

把马八个方向先预处理一下，然后就是基本的广搜了。。弄一个变量更新最小值，跟走迷宫其实区别不大

AC代码：

1. #include <bits/stdc++.h>
   
2. 
   
3. using namespace std;
   
4. 
   
5. struct note{
   
6. int x;
   
7. int y;
   
8. 
   
9. };
   
10. 
    
11. int maps[401][401];
    
12. int k;
    
13. int n,m,startx,starty;
    
14. int s;
    
15. int tx,ty;
    
16. int i,j;
    
17. int next[8][2] = {{2,1},{2,-1},{1,2},{1,-2},{-1,2},{-1,-2},{-2,1},{-2,-1}};
    
18. int main()
    
19. {
    
20.     struct note que[40001];
    
21.     memset(maps,-1,sizeof(maps));
    
22.     int head = 1;
    
23.     int tail = 1;
    
24.     scanf("%d%d%d%d",&n,&m,&startx,&starty);
    
25.     tail++;
    
26.     que[tail].x = startx;
    
27.     que[tail].y = starty;
    
28.     maps[que[tail].x][que[tail].y] = 0;
    
29.     while(head < tail)
    
30.     {
    
31.         head++;
    
32.         s = maps[que[head].x][que[head].y] + 1;
    
33.         for(k = 0;k < 8;k++)
    
34.         {
    
35.            tx = que[head].x + next[k][0]; ty = que[head].y + next[k][1];
    
36.            if(maps[tx][ty] == -1 && tx >= 1 && tx <= n && ty >= 1 && ty <= m)
    
37.            {
    
38.                tail++;
    
39.                que[tail].x = tx;
    
40.                que[tail].y = ty;
    
41.                maps[tx][ty] = s;
    
42.            }
    
43.         }
    
44. 
    
45.     }
    
46.     for(i = 1;i <= n;i++)
    
47.     {
    
48.         for(j = 1;j <= m;j++)
    
49.         {
    
50.             printf("%-5d",maps[i][j]);
    
51.         }
    
52.         printf("\n");
    
53.     }
    
54. 
    
55. return 0;
    
56. }
    

复制代码

---

作者: 刘伟杰    时间: 2018-10-19 19:20
luogu P2404 自然数的拆分问题

这题以前做过一个类似的。。。但到现在都有点没搞懂。。。

AC代码：

1. #include <bits/stdc++.h>
   
2. 
   
3. using namespace std;
   
4. 
   
5. int s[1000] = {1};
   
6. int n;
   
7. int k;
   
8. void print(int x)
   
9. {
   
10.     for(int i = 1;i < x;i++)
    
11.     {
    
12.         printf("%d+",s[i]);
    
13.     }
    
14.     printf("%d",s[x]);
    
15.     printf("\n");
    
16. }
    
17. void dfs(int x)
    
18. {
    
19.     for(int i = s[x-1];i <= k;i++)
    
20.     {
    
21.         if(i == n) continue;
    
22.         s[x] = i;
    
23.         k -= i;
    
24.         if(k == 0) print(x);
    
25.         else dfs(x+1);
    
26. 
    
27.         k+=i;
    
28.     }
    
29. }
    
30. 
    
31. int main()
    
32. {
    
33.     scanf("%d",&n);
    
34.     k = n;
    
35.     dfs(1);
    
36.     return 0;
    
37. }
    

复制代码

---

作者: 刘伟杰    时间: 2018-10-19 19:43
luogu P1238 走迷宫

3次才AC 第一次 50 第二次 80 第三次 100

分析原因：

1、上下左右看错？？？？

2、初始位置要标记。。。

3、这其实就是一道水题。。。。

迷宫类型问题的基本套路，记得剪枝，不然要tle的。。

AC代码：

1. #include <bits/stdc++.h>
   
2. 
   
3. using namespace std;
   
4. 
   
5. int maps[1000][1000];
   
6. int book[1000][1000];
   
7. int a[1000][3];
   
8. int next[4][2] = {{0,-1},{-1,0},{0,1},{1,0}};
   
9. int n,m;
   
10. int flag;
    
11. int p,q,sx,sy;
    
12. void print(int x)
    
13. {
    
14.     for(int i = 1;i < x;i++)
    
15.     {
    
16.         printf("(%d,%d)->",a[i][1],a[i][2]);
    
17.     }
    
18.     printf("(%d,%d)",a[x][1],a[x][2]);
    
19.     printf("\n");
    
20. }
    
21. void dfs(int x,int y,int step)
    
22. {
    
23.     int tx,ty;
    
24.     if(x == p && y == q)
    
25.     {
    
26.         flag = 1;
    
27.         print(step);
    
28.         return;
    
29.     }
    
30.     for(int k = 0;k <= 3;k++)
    
31.     {
    
32.         tx = x + next[k][0];
    
33.         ty = y + next[k][1];
    
34. 
    
35.         if(tx < 1 || tx > n || ty < 1 || ty > m) continue;
    
36. 
    
37.         if(book[tx][ty] == 0 && maps[tx][ty] == 1)
    
38.         {
    
39.             book[tx][ty] = 1;
    
40.             a[step+1][1] = tx;
    
41.             a[step+1][2] = ty;
    
42.             dfs(tx,ty,step+1);
    
43.             book[tx][ty] = 0;
    
44.         }
    
45.     }
    
46. }
    
47. int main()
    
48. {
    
49.     int i,j;
    
50.     scanf("%d%d",&n,&m);
    
51.     for(i = 1;i <= n;i++)
    
52.     {
    
53.         for(j = 1;j <= m;j++)
    
54.         {
    
55.             scanf("%d",&maps[i][j]);
    
56.         }
    
57.     }
    
58.     scanf("%d%d",&sx,&sy);
    
59.     scanf("%d%d",&p,&q);
    
60.     a[1][1] = sx;
    
61.     a[1][2] = sy;
    
62.     book[sx][sy] = 1;
    
63.     dfs(sx,sy,1);
    
64.     if(flag == 0)
    
65.     {
    
66.         printf("-1");
    
67.     }
    
68.     return 0;
    
69. }
    

复制代码

---

作者: 刘伟杰    时间: 2018-10-26 19:23
luogu P1233 木棍加工

先排序，再寻找最大不上升序列

贪心思想。。。没用dp。

1. #include <bits/stdc++.h>
   
2. 
   
3. using namespace std;
   
4. 
   
5. struct Mugun{
   
6.     int l;
   
7.     int w;
   
8.     int book;
   
9. }m[100000];
   
10. 
    
11. int n;
    
12. int ans = 0;
    
13. 
    
14. int cmp(struct Mugun a,struct Mugun b)
    
15. {
    
16.     return a.l > b.l;
    
17.     if(a.l == b.l)
    
18.         return a.w > b.w;
    
19. }
    
20. int temp;
    
21. int main()
    
22. {
    
23.     scanf("%d",&n);
    
24.     for(int i = 1;i <= n;i++)
    
25.     {
    
26.         scanf("%d%d",&m[i].l,&m[i].w);
    
27.         m[i].book = 0;
    
28.     }
    
29.     sort(m+1,m+1+n,cmp);
    
30.     for(int i = 1;i <= n;i++)
    
31.     {
    
32.         if(m[i].book == 0)
    
33.         {
    
34.             temp = m[i].w;
    
35.             for(int j = i+1;j <= n;j++)
    
36.             {
    
37.                 if(m[j].w<=temp&&m[j].book == 0)
    
38.                 {
    
39.                     m[j].book = 1;
    
40.                     temp = m[j].w;
    
41.                 }
    
42.             }
    
43.         }
    
44.     }
    
45.     for(int i = 1;i <= n;i++)
    
46.     {
    
47.         if(m[i].book == 0)
    
48.         {
    
49.             ans++;
    
50.         }
    
51.     }
    
52.     printf("%d",ans);
    
53. 
    
54. 
    
55. 
    
56. 
    
57.     return 0;
    
58. }
    

复制代码

---

作者: 刘伟杰    时间: 2018-10-26 19:24
luogu P1216 数字三角形

DP。。。吧

1. #include <bits/stdc++.h>
   
2. 
   
3. using namespace std;
   
4. 
   
5. int n,a[1002],i,j,ans,p;
   
6. 
   
7. int main()
   
8. {
   
9.     scanf("%d",&n);
   
10.         for(i=n;i;i--)
    
11.                 for(j=i;j<=n;j++)
    
12.                         scanf("%d",&p),a[j]=max(a[j],a[j+1])+p;
    
13.         for(i=1;i<=n;i++)
    
14.         ans=max(ans,a[i]);
    
15.         printf("%d",ans);
    
16.         return 0;
    
17. }
    

复制代码

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2