8.2做题记录

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 struct node{
 4     int x,y,z,s;
 5 }f[1005];
 6 int a[4],l,ans,dp[1005];
 7 bool cmp(node c,node d)
 8 {
 9     return c.x<=d.x;
10 }
11 bool big(int x,int y)
12 {
13     return x>y;
14 }
15 int main()
16 {
17     freopen("tower.in","r",stdin);
18     freopen("tower.out","w",stdout);
19     int n;
20     cin>>n;
21     for(int i=1;i<=n;i++)
22     {
23         cin>>a[1]>>a[2]>>a[3];
24         sort(a+1,a+4,big);
25         f[++l]={a[1],a[2],a[3],a[1]*a[2]};
26         f[++l]={a[1],a[3],a[2],a[1]*a[3]};
27         f[++l]={a[2],a[3],a[1],a[2]*a[3]};
28     }
29     sort(f+1,f+l+1,cmp);
30     for(int i=1;i<=l;i++)
31     {
32         dp[i]=f[i].z;
33         for(int j=i;j>=1;j--)
34         {
35             if(f[j].x<f[i].x && f[j].y<f[i].y)
36                 dp[i]=max(dp[i],dp[j]+f[i].z);
37         } 
38         ans=max(ans,dp[i]);
39     }
40     cout<<ans;
41     return 0;
42 }

 1 #include<bits/stdc++.h>
 2 typedef long long ll;
 3 using namespace std;
 4 ll dp[3][1005][1005],f[3][1005][1005];
 5 int main()
 6 {
 7     freopen("tlrw.in","r",stdin);
 8     freopen("tlrw.out","w",stdout);
 9     ll n;
10     cin>>n;
11     for(int i=1;i<=n;i++)
12         for(int j=1;j<=n;j++)
13         {
14             ll x;
15             cin>>x;
16             while(x%2==0)
17             {
18                 dp[1][i][j]++;
19                 x/=2;
20             }
21             while(x%5==0)
22             {
23                 dp[2][i][j]++;
24                 x/=5;
25             }
26         }
27     for(int i=1;i<=n;i++)
28         for(int j=1;j<=n;j++)
29         {
30             if(i==1&&j==1)
31             {
32                 f[1][i][j]=dp[1][i][j];
33                 f[2][i][j]=dp[2][i][j];
34             }
35             else if(i==1)
36             {
37                 f[1][i][j]=dp[1][i][j]+f[1][i][j-1];
38                 f[2][i][j]=dp[2][i][j]+f[2][i][j-1];
39             }
40             else if(j==1)
41             {
42                 f[1][i][j]=dp[1][i][j]+f[1][i-1][j];
43                 f[2][i][j]=dp[2][i][j]+f[2][i-1][j];
44             }
45             else
46             {
47                 f[1][i][j]=dp[1][i][j]+min(f[1][i][j-1],f[1][i-1][j]);
48                 f[2][i][j]=dp[2][i][j]+min(f[2][i][j-1],f[2][i-1][j]);
49             }
50         }
51     cout<<min(f[1][n][n],f[2][n][n]);
52     fclose(stdin);
53     fclose(stdout);
54     return 0;
55 }

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,a[5005],v[5005],ans,m;
 4 int main()
 5 {
 6     freopen("box.in","r",stdin);
 7     freopen("box.ans","w",stdout);
 8     ios::sync_with_stdio(false);
 9     cin>>n;
10     for (int i=1;i<=n;i++) cin>>a[i];
11     sort(a+1,a+n+1);
12     for (int i=1;i<=n;i++)
13         if(!v[i])
14         {
15             ans++;
16                 m=1;
17             for (int j=i+1;j<=n;j++)
18             if (!v[j]&&a[j]>=m)
19             {
20                 v[j]=1;
21                 m++;
22             }
23         }
24     cout<<ans<<endl;
25     fclose(stdin);
26     fclose(stdout);
27     return 0;
28 }