第八周 7.5-7.11

7.5-7.6

考数分背英语没码程序。

7.7

什么都没干。

7.8

HDU 2602 Bone Collector 01背包裸题

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 using namespace std;
 6 int cost[1001],value[1001],f[1001][1001];
 7 
 8 int main(void)
 9 {
10     int T;cin>>T;
11     while(T--)
12     {
13         memset(f,0,sizeof(f));
14         int N,V; scanf("%d%d",&N,&V);
15         for(int i=1;i<=N;i++) scanf("%d",value+i);
16         for(int i=1;i<=N;i++) scanf("%d",cost+i);
17         for(int i=1;i<=N;i++)
18             for(int j=0;j<=V;j++)
19                 if(cost[i]<=j) f[i][j]=max(f[i-1][j],f[i-1][j-cost[i]]+value[i]);
20                 else f[i][j]=f[i-1][j];
21         printf("%d
",f[N][V]);
22     }
23     return 0;
24 }

Aguin

设想是简单过下背包后dp先放。看下字符串。

然而此阶段抽时间码题真不容易。毕竟高代还是有点慌。

7.9

HDU 2602 Bone Collector 滚动数组

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 using namespace std;
 6 int cost[1001],value[1001],f[1001];
 7 
 8 int main(void)
 9 {
10     int T;cin>>T;
11     while(T--)
12     {
13         memset(f,0,sizeof(f));
14         int N,V; scanf("%d%d",&N,&V);
15         for(int i=1;i<=N;i++) scanf("%d",value+i);
16         for(int i=1;i<=N;i++) scanf("%d",cost+i);
17         for(int i=1;i<=N;i++)
18             for(int j=V;j>=cost[i];j--)
19                 f[j]=max(f[j],f[j-cost[i]]+value[i]);
20         printf("%d
",f[V]);
21     }
22     return 0;
23 }

Aguin

7.10

什么都没干。

7.11

打了个BC。又爆0了。不过感觉这次的题可以做- -

HDU5280 Senior's Array

过了然被骇。（补题的时候一个地方i写成1找了好久QAQ

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <algorithm>
 4 using namespace std;
 5 long long sum[1001][1001];
 6 int a[1001];
 7 
 8 int main(void)
 9 {
10     int T;cin>>T;
11     while(T--)
12     {
13         int n,p; scanf("%d%d",&n,&p);
14         for(int i=1;i<=n;i++) scanf("%d",a+i);
15         long long ans=-1000000000000LL;
16         for(int i=1;i<=n;i++)
17         {
18             int m;
19             for(int j=i;j<=n;j++)
20             {
21                 if(j==i) m=sum[i][j]=a[i];
22                 else sum[i][j]=sum[i][j-1]+a[j];
23                 if(a[j]<m) m=a[j];
24                 if(i==1&&j==n) ans=max(ans,sum[i][j]-m+p);
25                 else ans=max(ans,sum[i][j]-m+max(m,p));
26             }
27         }
28         printf("%I64d
",ans);
29     }
30     return 0;
31 }

Aguin

题解有个O(n)的dp方法。挖个坑。

HDU5281 Senior's Gun

早早的过了。然而clarification里有人喊数据错了。

过了一会就rejudge了。然后我终测就跪了。

（和出题人错一块去了？？

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <algorithm>
 4 using namespace std;
 5 int a[100000+10],b[100000+10];
 6 
 7 int main(void)
 8 {
 9     int T;cin>>T;
10     while(T--)
11     {
12         int n,m; scanf("%d%d",&n,&m);
13         for(int i=1;i<=n;i++) scanf("%d",a+i);
14         for(int i=1;i<=m;i++) scanf("%d",b+i);
15         sort(a+1,a+n+1); sort(b+1,b+m+1);
16         long long sum1=0,sum2=0;
17         for(int i=0;i<min(m,n);i++)
18         {
19             if(a[n-i]>=b[1+i])
20             {
21                 sum1+=a[n-i];
22                 sum2+=b[1+i];
23             }
24             else break;
25         }
26         printf("%I64d
",sum1-sum2);
27     }
28     return 0;
29 }

Aguin

万恶考试。

结果背包也没看。BC待补。