爱奇艺初赛代码

好久没上博客了顺便把爱奇艺初赛的代码也贴了吧……

A题是个01背包

做了一个不大不小的优化就是把v的含义变成了剩余的体积

因为每个物品的体积也太大了直接用差比较好用

（这个输入方式真的神奇……）

 1 #include<bits/stdc++.h>
 2 #define cl(a,b) memset(a,b,sizeof(a))
 3 #define debug(x) cerr<<#x<<"=="<<(x)<<endl
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     //freopen("in,txt","r",stdin);
 9     int n,v,w,now=0,ans=0;
10     scanf("%d",&n);
11     vector<int>dp(n+1,0);
12     while(scanf("%d%d",&v,&w) != EOF)
13     {
14         for(int i=min(now,n-v);i>=0;i--)
15         {
16             dp[i+v]=max(dp[i+v],dp[i]+w);
17             now=max(now,i+v);
18             ans=max(ans,dp[i+v]);
19         }
20     }
21     printf("%d
",ans);
22     return 0;
23 }/*
24 
25 10 5 7 2 3 8 10 3 4
26 
27 */

B题应该是找个合适长度

直接二分

记得数据范围很大所以开的vector

顺手练一下auto的用法

（stl真好用……）

 1 #include<bits/stdc++.h>
 2 #define cl(a,b) memset(a,b,sizeof(a))
 3 #define debug(x) cerr<<#x<<"=="<<(x)<<endl
 4 using namespace std;
 5 typedef long long ll;
 6 
 7 vector<int>ans;
 8 
 9 ll n,t,l,r,x,sum;
10 
11 void solve()
12 {
13     while(l<=r)
14     {
15         ll mid=(l+r)/2;
16         if(mid==0) break;
17         sum=0;
18         for(auto it:ans)
19         {
20             sum+=it/mid;
21         }
22         if (sum>=n) l=mid+1;
23         else r=mid-1;
24     }
25 }
26 
27 int main()
28 {
29     cin>>n;
30     l=0,r=1e10;
31     ans.clear();
32     while(cin>>x)
33     {
34         r=max(x,r);
35         ans.push_back(x);
36     }
37     solve();
38     cout<<r<<endl;
39     return 0;
40 }/*
41 
42 3
43 3 1 5
44 
45 */

C是一个裸的区间dp

直接描述一遍题意就可以了

（感谢放牛区间dp的讲解）

 1 #include<bits/stdc++.h>
 2 #define cl(a,b) memset(a,b,sizeof(a))
 3 #define debug(x) cerr<<#x<<"=="<<(x)<<endl
 4 using namespace std;
 5 typedef long long ll;
 6 
 7 const int maxn=500+10;
 8 
 9 int a[maxn];
10 int dp[maxn][maxn];
11 
12 int dfs(int l,int r)
13 {
14     if(l>r) return 0;
15     if(dp[l][r] == -1)
16     {
17         for(int i=l;i<=r;i++)
18         {
19             dp[l][r]=max(dp[l][r],dfs(l,i-1)+dfs(i+1,r)+a[i]*a[l-1]*a[r+1]);
20         }
21     }
22     return dp[l][r];
23 }
24 
25 int main()
26 {
27 //    freopen("in,txt","r",stdin);
28     int n,x;
29     scanf("%d",&n);
30     cl(dp,-1),cl(a,0);
31     for(int i=1;i<=n;i++)
32     {
33         scanf("%d",&a[i]);
34     }
35     a[0]=a[n+1]=1;
36     printf("%d
",dfs(1,n));
37     return 0;
38 }/*
39 
40 3
41 3 1 5
42 
43 */

D题是插头dp

因为当时才看过kuangbin的博客

很惊奇出了原题直接贴了代码……

贴个链接吧：http://www.cnblogs.com/kuangbin/archive/2012/09/30/2709114.html