暑假第二十测

题解：

第一题：

这道题最先想到的就是贪心，但是纯贪心明显是不对的，
如 2 2 1 3 3 贪心结果为2 2 （133）但实际是2 （21） 3 3 。
所以这样是不对的。
那要怎么做呢.....考虑用dp.........
阶段应该是明显的就是第几个数，我们还是要用到贪心的思想，
就是保证在最后面的合起来的数尽可能的小
我们用f[i]表示到第i这个数的最多的组数。
b[i]表示从1到i的所有数的和（很明显如果合并从k到i那么合并后的数就是b[i]-b[k]）；
s[i]表示到第i这个阶段的最后一个数的大小。
所以转移方程就是：f[i]=max(f[k]+1); (b[i]-b[k]>=s[k])
s[i]=b[i]-b[k];

#include<bits/stdc++.h>
using namespace std;
const int inf = 1e8;
const int M = 5005;
int dp[M], tot;
long long res[M], h[M], sum[M];
int main(){
    freopen("tower.in","r",stdin);
    freopen("tower.out","w",stdout);
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)scanf("%I64d", &h[i]), sum[i] = sum[i - 1] + h[i];
    for(int i = 1; i <= n; i++)
        for(int j = 0; j < i; j++){
            if(res[j] <= sum[i] - sum[j]){
                if(dp[j] + 1 > dp[i])dp[i] = dp[j] + 1, res[i] = sum[i] - sum[j];
                else if(dp[j] + 1 == dp[i])res[i] = min(sum[i] - sum[j], res[i]);
            }
        }
    printf("%d\n",n - dp[n]);
}

 

第二题：

动态规划，定义f[i][j]代表在i时间，能力值为j的最多工作次数。

对应最后三种选择：

①不作为 f[i][j]=f[i-1][j],

②上课 f[i][j]=f[上课前一个时刻][任意],

③做工作 f[i][j]=f[i-po[j]][j]+1 （po[j]为能力值<=j的工作一次的最短用时）。

对于②可以在预处理出ke[i][j]在i时刻结束，能力值达到j的课程的最晚开始时间。dp过程中处理出g[i]=max{f[i][j]}。

g[t]即为答案。

#include<bits/stdc++.h>
using namespace std;
const int inf = 1e8;
const int M = 10005;
int cl[M], clt[M], mt[M], dp[M][205];
struct node{int c, d;}p[M];
/*bool cmp1(node a, node b){
    return a.c + a.d < b.c + b.d;
}*/
bool cmp2(node a, node b){
    return a.c < b.c;
}

int main(){
    freopen("wrk.in","r",stdin);
    freopen("wrk.out","w",stdout);
    int T, S, N, A = 0, ans = 0;
    int m, l, a;
    scanf("%d%d%d", &T, &S, &N);
    for(int i = 1; i <= S; i++){
        scanf("%d%d%d", &m, &l, &a);
        cl[m] = a, clt[m] = l;
        //cls[a].push_back((node){m, l});
        A = max(A, a);
    }
    /*for(int a = 1; a <= A; a++)
        if(cls[a].size() > 1)sort(cls[a].begin(), cls[a].end(), cmp1);
    */
    for(int i = 1; i <= N; i++){
        scanf("%d%d", &p[i].c, &p[i].d);
    }    
    sort(p + 1, p + 1 + N, cmp2);
    memset(mt, 127, sizeof(mt));
    for(int i = 1; i <= N; i++){
        if(p[i].c != p[i - 1].c){
            for(int j = p[i - 1].c + 1; j <= p[i].c; j++)mt[j] = mt[p[i - 1].c];
        }
        mt[p[i].c] = min(mt[p[i].c], p[i].d);
    }
    for(int j = p[N].c + 1; j <= A; j++)mt[j] = mt[p[N].c];
    memset(dp, -1, sizeof(dp));
    dp[0][1] = 0;
    for(int t = 0; t <= T; t++){
        for(int p = 1; p <= A; p++){
            if(dp[t][p] == -1)continue;
            dp[t + 1][p] = max(dp[t + 1][p], dp[t][p]);
            if(mt[p] < inf && t + mt[p] <= T)dp[t + mt[p]][p] = max(dp[t + mt[p]][p], dp[t][p] + 1);
            if(cl[t] > p)dp[t + clt[t]][cl[t]] = max(dp[t + clt[t]][cl[t]], dp[t][p]);
            //printf("%d %d %d\n", t, p, dp[t][p]);
        }
    }
    for(int p = 1; p <= A; p++)
        ans = max(ans, dp[T][p]);
    printf("%d\n", ans);    
    
    
}

 

 

第三题

二分答案。
枚举距离特殊点最近的建造的树洞是哪一个，记为X。
在图中删除能够在二分的时间内到达该树洞X的所有点。
此时图变为若干条独立的链，直接求最少需要的树洞数。
在所有枚举的情况中取最小值，与K比较确定二分范围变化。

#include<bits/stdc++.h>
using namespace std;

const int M = 2005;
#define ex(i, u) for(int i = h[u]; i; i = G[i].nxt)
int h[M], dep[M], dis[M][M], n, tot, m, k, root, du[M];
bool vis[M];
struct edge{int v,nxt;}G[ M << 2];
void add(int u, int v){G[++tot].v=v,G[tot].nxt=h[u],h[u]=tot;}
void bfs(int st){
    queue <int> Q;
    Q.push(st);
    while(!Q.empty()){
        int u = Q.front(); Q.pop();
        ex(i, u){
            int v = G[i].v;
            if(!dis[st][v] && v != st){
                dis[st][v] = dis[st][u] + 1;
                Q.push(v);
            }
        }
    }
    
}
int tl;
void dfs(int u){
    tl += (vis[u] = 1);
    ex(i, u){
        int v = G[i].v;
        if(!vis[v])dfs(v);
    }
}


int work(int now, int len){
    memset(vis, 0, sizeof(vis));
    int ans = 0;
    for(int i = 1; i <= n; i++)
        if(dis[now][i] <= len)vis[i] = 1;
    for(int i = 1; i <= n; i++)
        if(!vis[i]){
            dfs(i); int tt = ceil(1.0*tl/(2*len+1));
            ans += tt; tl = 0; 
        }
    return ans;
}

bool check(int mid){
    int ans = 1e8;
    for(int i = 1; i <= n; i++)
        if(dis[root][i] <= mid)
            ans = min(ans, work(i, mid));
    return ans + 1 <= k;
}


int main(){
    freopen("holes.in","r",stdin);
    freopen("holes.out","w",stdout);
    int ans = 0;
    scanf("%d%d%d", &n, &m, &k);
    int u, v;
    for(int i = 1; i <= m; i++){
        scanf("%d%d", &u, &v);
        add(u, v);du[u]++;
        add(v, u);du[v]++;
    }
    for(int i = 1; i <= n; i++)
        if(du[i] > 2){
            root = i; break;
        }
    if(!root){
        int ans = ceil(1.0*(n - k)/(k << 1));
        printf("%d\n", ans);
        return 0;
    }
    for(int i = 1; i <= n; i++)bfs(i);
    int lf = 1, rg = n;
    while(lf <= rg){
        int mid = (lf + rg) >> 1;
        if(check(mid))ans = mid, rg = mid - 1;
        else lf = mid + 1;
    }
    printf("%d\n", ans);
}