light oj---1004 - Monkey Banana Problem

1. #include<stdio.h>
2. #include<string.h>
3. #define LL long long
4. LL dp[210][210],num[210][210],n;
6. LL max(LL a,LL b)
7.  {
8.      if(a>b) return a;
9.      return b;
10.  }
12. LL call(LL a,LL b)
13.  {
14.      if(num[a][b]==0) return 0;
16.      if(dp[a][b]!=-1) return dp[a][b];
19.      LL ret=num[a][b];
20.      if(a<=n)
21.       ret+=max(call(a-1,b),call(a-1,b-1));
22.      else
23.      ret+=max(call(a-1,b),call(a-1,b+1));
25.      return dp[a][b]=ret;
26.  }
28. int main()
29.  {
30.      int t;
31.      scanf("%d",&t);
33.      for(int i=1;i<=t;i++)
34.       {
36.           scanf("%lld",&n);
37.           for(int j=0;j<=200;j++)
38.             for(int k=0;k<=200;k++)
39.               {
40.                    num[j][k]=0;
41.                    dp[j][k]=-1;
42.               }
43.           for(int j=1;j<n;j++)
44.            for(int k=1;k<=j;k++)
45.              scanf("%lld",&num[j][k]);
46.           for(int j=n;j<2*n;j++)
47.            for(int k=1;k<=2*n-j;k++)
48.              scanf("%lld",&num[j][k]);
51.           LL ans=num[2*n-1][1];
52.           ans+=max(call(2*n-2,1),call(2*n-2,2));
53.           printf("Case %d: %lld\n",i,ans);
56.       }
57.       return 0;
58.  }

ligjt oj---1003 - Drunk

1. #include <algorithm>
2. #include <cassert>
3. #include <cctype>
4. #include <cfloat>
5. #include <climits>
6. #include <cmath>
7. #include <cstdio>
8. #include <cstdlib>
9. #include <cstring>
10. #include <iostream>
11. #include <limits>
12. #include <map>
13. #include <queue>
14. #include <set>
15. #include <sstream>
16. #include <stack>
17. #include <string>
18. #include <utility>
19. #include <vector>
20. #define G getchar()
21. #define FOR(i,t) for(i=1;i<=t;i++)
22. #define FORO(j,n) for(j=0;j<n;j++)
23. #define EPS DBL_EPSILON
24. #define abs(x) (((x)<0)?-(x):(x))
25. #define ZERO(x) (abs(x) < EPS)
26. #define EQ(a,b) (ZERO((a)-(b)))
27. #define max(a,b) (a)>(b)?(a):(b)
28. #define min(a,b) (a)<(b)?(a):(b)
29. #define memo(a,v) memset(a,v,sizeof(a))
30. #define PI 2*acos(0.0)
31. #define all(a) a.begin(),a.end()
32. #define EPS 1e-8
33. #define INF -1U >> 1
34. #define LL int int
35. #define NL puts("")
36. #define MAX 30001
37. using namespace std;
38. map<string ,int >m;
39. vector<int >v[20010];
40. //string st1,st2;
41. char in[20010];
42. int j=0;
43. void fix(int i)
44. {
45.     int k;
46.     in[i]=-1;
47.     FORO(k,v[i].size())
48.            {
49.                in[v[i][k]]--;
50.            }
51. }
53. bool comp(int a,int b)
54.  {
55.      if(a>b) return true;
56.      return false;
57.  }
59. int main()
60.  {
61.      int i,t;
62.      scanf("%d",&t);
64.      FOR(i,t)
65.       {
66.           m.clear();
67.           memo(in,0);
69.          int a,k;
70.          j=0;
71.           scanf("%d",&a);
72.           while(a--)
73.            {
74.                G;
75.                char st1[100],st2[100];
76.                scanf("%s %s",&st1,&st2);
77.                if(!(m.count(st1)>0))
78.                 m[st1]=j++;
79.                if(!(m.count(st2)>0))
80.                 m[st2]=j++;
81.                v[m[st1]].push_back(m[st2]);
82.                in[m[st2]]++;
83.            }
84.           int fin;
85.          fin = 0;
87.          while(fin<j)
88.           {
89.             FORO(k,j)
90.              if(in[k]==0)
91.                   fix(k);
92.             fin++;
93.           }
94.          //FORO(k,j) printf("%d ",in[k]);
95.          //NL;
96.          sort(in,in+j,comp);
98.          if(in[1]>0)
99.           printf("Case %d: No\n",i);
100.          else printf("Case %d: Yes\n",i);
101.        FORO(k,j)
102.         v[k].clear();
104.       }
105.       return 0;
106.  }