Day1下午解题报告

阅读量：5884 次

发布时间：2019-06-19

本文共 4924 字，大约阅读时间需要 16 分钟。

预计分数：0+30+30=60

实际分数：0+30+40=70

T1水题(water)

贪心，按长度排序，

对于第一幅牌里面的，在第二个里面，找一个长度小于，高度最接近的牌

进行覆盖。

考场上的我离正解只差一个小于号之遥。。。。。。。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 using namespace std; 7 int n; 8 multiset 
           
             s; 9 struct node { int x,y;} a[100005],b[100005];10 int cmp(node i,node j) { return i.x
            
             =b[k].x&&k

::iterator it=s.upper_bound(a[i].y);35 if (it==s.begin()) continue; it--;36 ans++; s.erase(it);37 }38 printf("%d\n",ans);39 }40 return 0;41 }

View Code

T2下午梦境(dream)

不会做，手玩30分

正解

dp||爆搜

1 2 4 8 ...

1 3 7 15 31 ...

int(log(n)/log(2))+1

方案总数：dp，搜索

2^0+2^1+...+2^k = O(n)

k=log(n)

dfs(Max,Sum,S) // Max金币最大值，Sum所有金币的和，S金币的数量

dp[i][j][k] 当前有i个金币，金币和是j，最大的金币k。

if (dp[i][j][k]) 枚举下一枚金币是啥。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 const int MAXN=1e6; 7 inline int read() 8 { 9     char c=getchar();int flag=1,x=0;10     while(c<'0'||c>'9')    {
    if(c=='-')    flag=-1;c=getchar();}11     while(c>='0'&&c<='9')     x=x*10+c-48,c=getchar();return x*flag;12 }13 int n;14 int main()15 {16     //freopen("dream.in","r",stdin);17     //freopen("dream.out","w",stdout);18     n=read();19     if(n==0)    printf("0 1");20     if(n==1)    printf("1 1");21     if(n==2)    printf("2 1");22     if(n==3)    printf("2 1");23     if(n==4)    printf("3 1");24     if(n==5)    printf("3 2");25     if(n==6)    printf("3 2");26     if(n==7)    printf("3 1");27     if(n==8)    printf("4 8");28     if(n==9)    printf("4 8");29     if(n==10)    printf("4 8");30     if(n>10)    printf("5 6");31     return 0;32 }

View Code

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 using namespace std; 7 int n,sum,ans,dp[1005][1005],DP[1005][1005],i,j,k,l; 8 int main() 9 {10     freopen("dream.in","r",stdin);11     freopen("dream.out","w",stdout);12     scanf("%d",&n);13     sum=int(log(n)/log(2)+0.000000001)+1;14     dp[1][1]=1;15     for (i=1; i

标程

T3动态规划(dp)

题目描述

LYK在学习dp，有一天它看到了一道关于dp的题目。

这个题目是这个样子的：一开始有n个数，一段区间的价值为这段区间相同的数的对数。我们想把这n个数切成恰好k段区间。之后这n个数的价值为这k段区间的价值和。我们想让最终这n个数的价值和尽可能少。

例如6个数1,1,2,2,3,3要切成3段，一个好方法是切成[1],[1,2],[2,3,3]，这样只有第三个区间有1的价值。因此这6个数的价值为1。

LYK并不会做，丢给了你。

输入输出格式

输入格式：

第一行两个数n,k。

接下来一行n个数ai表示这n个数。

输出格式：

一个数表示答案。

输入输出样例

输入样例#1：

10 21 2 1 2 1 2 1 2 1 2

输出样例#1：

说明

对于30%的数据n<=10。

对于60%的数据n<=1000。

对于100%的数据1<=n<=100000,1<=k<=min(n,20),1<=ai<=n。

其中有30%的数据满足ai完全相同均匀分布在所有数据中。

考场上我想出60分的dp了

但是我感觉不对，直觉告诉我一定不对，。

但实际上是对的mmp。。。。。

打了30分暴力走人，，

正解：

dp[i][j] 1~i 切了j刀，的最优解

dp[i][j]=min{dp[k][j-1]+sum(k+1,i)}

可以证明这个转移方程具有单调性

20*n^2的简单dp -> 在固定j的情况下随着i的增大，k不降 -> 分治求dp值

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #define N 1000011 5 #define min(x, y) ((x) < (y) ? (x) : (y)) 6 #define max(x, y) ((x) > (y) ? (x) : (y)) 7 using namespace std; 8 int n, q, ans; 9 int f[N];10 11 struct node12 {13     int x, y, z;14 }p[N], t[N];15 16 inline int read()17 {18     int x = 0, f = 1;19     char ch = getchar();20     for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;21     for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';22     return x * f;23 }24 25 inline bool cmp(node x, node y)26 {27     return x.z > y.z;28 }29 30 inline int find(int x)31 {32     return x == f[x] ? x : f[x] = find(f[x]);33 }34 35 inline bool check(int k)36 {37     int i, j, x, y, lmin, lmax, rmin, rmax;38     for(i = 1; i <= n + 1; i++) f[i] = i;39     for(i = 1; i <= k; i++) t[i] = p[i];40     std::sort(t + 1, t + k + 1, cmp);41     lmin = lmax = t[1].x;42     rmin = rmax = t[1].y;43     for(i = 2; i <= k; i++)44     {45         if(t[i].z < t[i - 1].z)46         {47             if(find(lmax) > rmin) return 1;48             for(j = find(lmin); j <= rmax; j++)49                 f[find(j)] = find(rmax + 1);50             lmin = lmax = t[i].x;51             rmin = rmax = t[i].y;52         }53         else54         {55             lmin = min(lmin, t[i].x);56             lmax = max(lmax, t[i].x);57             rmin = min(rmin, t[i].y);58             rmax = max(rmax, t[i].y);59             if(lmax > rmin) return 1;60         }61     }62 //    cout<
         
          <
          
            rmin) return 1;64     return 0;65 }66 67 int main()68 {69     freopen("number.in","r",stdin);70     freopen("number.out","w",stdout);71     int i, x, y, mid;72     n = read();73     q = read();74     for(i = 1; i <= q; i++)75         p[i].x = read(), p[i].y = read(), p[i].z = read();76     x = 1, y = q;77     //cout<
           
            <
            
             > 1;83 if(check(mid)) ans = mid, y = mid - 1;84 else x = mid + 1;85 }86 printf("%d\n", ans);87 return 0;88 }