头像

ACwisher

Idealistoj neniam maljuniĝas.




离线:2小时前



ACwisher
3小时前

神仙的题解

$dp[i][j]$ 表示将前 $i$ 种物品放入容量为 $j$ 的背包中所得到的最大价值
$dp[i][j]$ = $max($不放入物品 $i$,放入1个物品 $i$,放入2个物品 $i$, … , 放入 $k$ 个物品 i$)$
这里 $k$ 要满足:$k <= s, j - kv >= 0$

不放物品 i = $dp[i-1][j]$
放k个物品 i = $dp[i-1][j - kv] + kw$

$dp[i][j] = max(dp[i-1][j], dp[i-1][j-v] + w, dp[i-1][j-2v] + 2*w,…, dp[i-1][j-kv] + kw)$


实际上我们并不需要二维的dp数组,适当的调整循环条件,我们可以重复利用dp数组来保存上一轮的信息

我们令 $dp[j]$ 表示容量为 $j$ 的情况下,获得的最大价值
那么,针对每一类物品 $i$ ,我们都更新一下 $dp[m] –> dp[0]$ 的值,最后 $dp[m]$ 就是一个全局最优值

$dp[m] = max(dp[m], dp[m-v] + w, dp[m-2v] + 2*w, dp[m-3v] + 3w, …)$

接下来,我们把 $dp[0] –> dp[m]$ 写成下面这种形式
$dp[0], dp[v], dp[2v], dp[3v], … , dp[kv]$
$dp[1], dp[v+1], dp[2v+1], dp[3v+1], … , dp[kv+1]$
$dp[2], dp[v+2], dp[2v+2], dp[3v+2], … , dp[kv+2]$

$dp[j], dp[v+j], dp[2v+j], dp[3v+j], … , dp[kv+j]$
$显而易见,m 一定等于 kv + j,其中 0 \le j < v$
所以,我们可以把 dp 数组分成 $j$ 个类,每一类中的值,都是在同类之间转换得到的
也就是说,$dp[kv+j] 只依赖于 { dp[j], dp[v+j], dp[2v+j], dp[3v+j], … , dp[kv+j] }$


因为我们需要的是 ${ dp[j], dp[v+j], dp[2v+j], dp[3v+j], … , dp[kv+j] }$ 中的最大值,
可以通过维护一个单调队列来得到结果。这样的话,问题就变成了 $j$ 个单调队列的问题
所以,我们可以得到
$dp[j] = dp[j]$
$dp[j+v] = max(dp[j] + w, dp[j+v])$
$dp[j+2v] = max(dp[j] + 2w, dp[j+v] + w, dp[j+2v])$
$dp[j+3v] = max(dp[j] + 3w, dp[j+v] + 2w, dp[j+2v] + w, dp[j+3v])$

但是,这个队列中前面的数,每次都会增加一个 $w$ ,所以我们需要做一些转换
$dp[j] = dp[j]$
$dp[j+v] = max(dp[j], dp[j+v] - w) + w$
$dp[j+2v] = max(dp[j], dp[j+v] - w, dp[j+2v] - 2w) + 2w$
$dp[j+3v] = max(dp[j], dp[j+v] - w, dp[j+2v] - 2w, dp[j+3v] - 3w) + 3w$

这样,每次入队的值是 $dp[j+kv] - kw$


单调队列问题,最重要的两点
1)维护队列元素的个数,如果不能继续入队,弹出队头元素
2)维护队列的单调性,即:尾值 $\ge dp[j + kv] - kw$

本题中,队列中元素的个数应该为 $s+1$ 个,即 $0 - s$ 个物品 $i$

dalao的code:

#include <iostream>
#include <cstring>

using namespace std;

const int N = 20010;

int dp[N], pre[N], q[N];
int n, m;

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        memcpy(pre, dp, sizeof(dp));
        int v, w, s;
        cin >> v >> w >> s;
        for (int j = 0; j < v; ++j) {//维护v个单调队列,%v=j的体积类
            int head = 0, tail = -1;
            for (int k = j; k <= m; k += v) {//枚举每个j+kv
                if (head <= tail && k - s*v > q[head])
                    ++head;//太小了,q[head]不可能转移到k
                while (head <= tail && pre[q[tail]] - (q[tail] - j)/v * w <= pre[k] - (k - j)/v * w)
                    --tail;
                if (head <= tail) dp[k] = max(dp[k], pre[q[head]] + (k - q[head])/v * w);
                q[++tail] = k;
            }
        }
    }
    cout << dp[m] << endl;
    return 0;
}



ACwisher
13小时前

。。。1000变2000可还行。。。我直接从上一题拿来改,以为数据范围都一样只开了个longlong就跑了




NOIP2013 华容道

图论好题。

显然需要将白格移动到 $s$ 相邻格,然后交换 $s$ 与白格,再将白格移动到 $s$ 相邻格,然后交换 $s$ 与白格……最后一步将白格移动到 与 $s$ 相邻的 $t$ ,交换白格与 $s$。

我们考虑到,将格子 $a$ 从 $(i,j)$ 移动到相邻的格子 $b$,需要让白格先移动到 $b$,之后交换 $a$ 与白格。显然 $a$ 下一步还是要继续往其他方向移动的,所以白格仍然需要移动到格子 $a$ 的某个相邻格。

我们写了一个 bfs ,可以在白格在 $(ei,ej)$, s $(si,sj)$ 的时候处理一些值,接下来详细阐述。


现在所阐述的 bfs 是在代码中 $k=0,1,2,3$ 时的 bfs ,用于预处理建图。

设置状态 $(i,j,k)$ 表示 格子 $s$ 在 $(i,j)$ ,白格在 $(i,j)$ 的方向 $k$ 处。( $k$ : left right up down,用0,1,2,3表示)。

可以通过 bfs 计算出 状态 $(i,j,k)$ 时, 白格开始移动,移动到棋盘上任意一个格子 $(x,y)$ 的花费 $dis_{x,y}$。注意,在代码中,为了方便标记哪些是不可能移动到的点,将所有 $dis_{x,y}$ 都加一了,但在题解中 $dis_{x,y}$ 仍然是原先的值。

从状态 $(i,j,k)$ 转移到另一个状态,有两种情况。

  • 白格与 $s$ 交换,在状态 $(si,sj,k)$ 与 $(ei,ej,k\and 1)$ 之间连边 1。
  • 白格移动到了一个与 $s$ 相邻的位置 $(xx,yy)$ ,在状态 $(si,sj,k)$ 与状态 $(si,sj,i)$ 之间连边 $dis_{xx,yy}$.

如果要计算状态 $(x1,y1,k1)$ 到状态 $(x2,y2,k2)$ 之间的最小花费,只需要跑最短路即可。

也就是说,我们把状态作为点,花费作为边建图。


现在阐述的是在代码中 $k=4$ 时的 bfs,这是处理 白格到 初始格的相邻格 花费的 bfs。

仍然先处理出所有的 $dis_{x,y}$ , 意义与求法同 $k=0,1,2,3$ 时一样。将与 $s$ 相邻格的 $dis_{x,y}$ 赋值在 dist 上。

最后计算答案,只需要 spfa 计算 $(tx,ty,0/1/2/3)$ 到 $(sx,sy,0/1/2/3)$ 的最短路。

#include<bits/stdc++.h>
using namespace std;
const int N=35,M=4010;
int n,m,q,mp[N][N],dis[N][N],dist[M];
bool vis[M];
int e,to[M*5],nxt[M*5],val[M*5],hd[M];
int dx[5]={-1,1,0,0};
int dy[5]={0,0,-1,1};
void add(int x,int y,int w){ to[++e]=y; nxt[e]=hd[x]; val[e]=w; hd[x]=e; }
void bfs(int ei,int ej,int si,int sj,int dir){
    memset(dis,0,sizeof(dis));
    queue<pair<int,int> >q;
    q.push(make_pair(ei,ej)); dis[ei][ej]=1;
    while(!q.empty()){
        pair<int,int>w=q.front(); q.pop();
        int x=w.first,y=w.second;
        for(int i=0;i<4;i++){
            int xx=x+dx[i],yy=y+dy[i];
            if(!mp[xx][yy]||dis[xx][yy]||xx==si&&yy==sj) continue;
            dis[xx][yy]=dis[x][y]+1; q.push(make_pair(xx,yy));
        }
    }//白格向外疯狂移动处理步数
    if(dir==4) return;

    for(int i=0;i<4;i++){
        int xx=si+dx[i],yy=sj+dy[i];
        if((xx==ei&&yy==ej)||!dis[xx][yy]) continue;
        add(si*30*4+sj*4+dir,si*30*4+sj*4+i,dis[xx][yy]-1);//白格移动
    }
    add(si*30*4+sj*4+dir,ei*30*4+ej*4+(dir^1),1);//交换
    return;
}
void spfa(int x,int y){
    memset(dist,0x3f,sizeof(dist));
    memset(vis,0,sizeof(vis));

    queue<int>q;
    for(int i=0;i<4;i++){
        if(!dis[x+dx[i]][y+dy[i]]) continue;
        int id=x*30*4+y*4+i; q.push(id);
        dist[id]=dis[x+dx[i]][y+dy[i]]-1; vis[id]=1;
    }
    while(!q.empty()){
        int id=q.front(); q.pop(); vis[id]=0;
      //  cout<<id<<endl;
        for(int i=hd[id];i;i=nxt[i]){
            int nxid=to[i],nxval=val[i];
        //    cout<<"nxid: "<<nxid<<endl;
            if(dist[nxid]>dist[id]+nxval){
                dist[nxid]=dist[id]+nxval;
                if(vis[nxid]) continue;
                vis[nxid]=1; q.push(nxid);
            }
        }
    }
    return;
}
int main(){
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&mp[i][j]);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!mp[i][j]) continue;
            if(mp[i-1][j]) bfs(i-1,j,i,j,0);
            if(mp[i+1][j]) bfs(i+1,j,i,j,1);
            if(mp[i][j-1]) bfs(i,j-1,i,j,2);
            if(mp[i][j+1]) bfs(i,j+1,i,j,3);
        }
    }
    //预处理,建图
    while(q--){
        int ex,ey,sx,sy,tx,ty;
        scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&tx,&ty);
        if(sx==tx&&sy==ty){ puts("0"); continue; } 

        bfs(ex,ey,sx,sy,4); spfa(sx,sy); int ans=0x3f3f3f3f;
        for(int i=0;i<4;i++) ans=min(ans,dist[tx*30*4+ty*4+i]);
        (ans==0x3f3f3f3f)?puts("-1"):printf("%d\n",ans);
    }
    return 0;
}


新鲜事 原文

图片


新鲜事 原文

我连Div2C都不会啊 呜呜


新鲜事 原文

图片 图片 图片 图片 图片 图片 图片 图片 图片


新鲜事 原文

图片 图片 图片 图片 图片 图片 图片 图片 图片


新鲜事 原文

图片 图片 图片 图片 图片 图片 图片 图片 图片


新鲜事 原文

图片 图片 图片 图片 图片 图片 图片 图片 图片


新鲜事 原文

清晨:我要睡觉 我要颓废 早晨:IAKIOI 我踌躇满志 上午:md破模拟赛那么简单我还不会做我是傻逼是傻逼所有人都切了 中午:??电脑是什么??不管 我午休颓一会儿 下午:哦哦 艰难版模拟赛反正大家都不会 我去做点别的题……然后调一下午 晚上:人民自由了……靠我效率怎么那么低我今天一天在干嘛……快做快做快做题 深夜:来不及了快回寝室 --- 清晨:我要睡觉 我要颓废 ……