2022/4/17模拟

今天又模拟辣！

今天又起晚辣！

T1：

这是个模拟，所以对着大样例找规律就行了，就几行，不知道对不对。

但是找规律还是挺花时间的说，花了半个点之久（还是太菜了

T2：

最短路吧。

YbtOJ原题吧，不然我这废物怎么做得出来。

花了20分钟敲了个dijkstra，走了。

#include<cstdio>
#include<queue>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cctype>
#include<vector>
#include<string>
#include<climits>
#define mp(x,y) make_pair((x),(y))
using namespace std;
typedef pair<int,int> pir;
template <typename T>
inline void read(T &x){x=0;char ch=getchar();bool f=0;while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();if(f)x=-x;}
template <typename T,typename ...Args>
inline void read(T &tmp,Args &...tmps){read(tmp);read(tmps...);}
const int N = 1e4 + 5;
struct qwq{
    int dis,k,u;
    bool operator <(qwq A)const{return dis > A.dis;}    
    qwq(int a,int b,int c):dis(a),k(b),u(c) {}
};
vector<pir>g[N];
int n,m,dis[N][12],pre[N],K,vis[N][12];
vector<int>tot;
inline void dijkstra(){
    memset(dis,0x3f3f3f3f,sizeof(dis));
    dis[0][K] = 0;
    priority_queue<qwq>q;
    q.push(qwq(0,K,0));
    while(!q.empty()){
        qwq tmp = q.top();q.pop();
        if(vis[tmp.u][tmp.k])continue;
        vis[tmp.u][tmp.k] = 1;
        int u = tmp.u,k = tmp.k;
        for(pir tm : g[u]){
            int v = tm.first,w = tm.second;
            if(dis[u][k] + w < dis[v][k]){
                dis[v][k] = dis[u][k] + w;
                q.push(qwq(dis[v][k],k,v));    
            }
            if(k > 0 && dis[u][k] < dis[v][k-1]){
                dis[v][k-1] = dis[u][k];
                q.push(qwq(dis[v][k-1],k-1,v));    
            }
        }
    }
}
signed main(){
    freopen("overwatch.in","r",stdin);
    freopen("overwatch.out","w",stdout);
    read(n,m,K);
    for(int i=1;i<=m;++i){
        int u,v,t;
        read(u,v,t);
        g[u].push_back(mp(v,t));
        g[v].push_back(mp(u,t));    
    }
    dijkstra();
    int ans = INT_MAX;
    for(int i=0;i<=K;++i)ans = min(ans,dis[n-1][i]); 
    printf("%d",ans);
}

T3：

哇，这题好高级的样子。

上来看了一会儿，难道是链表+贪心？

再看了一会儿，这不纯纯区间dp吗，你个**。

既然题里说了只能合并相邻两个，那么其实区间长度应该是偶数的，然后就是板子套上去。

但是！这题好像并没有那么简单，答案并不一定是 dp[1][n]，因为有很多没统计的区间啊，所以我们要一个个合并上去。

嗯就这样，好像和答案解法一样，溜了溜了。

#include<cstdio>
#include<queue>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cctype>
#include<vector>
#include<string>
#include<climits>
#define R register
using namespace std;
template <class T>
inline void read(T &x){x=0;char ch=getchar();bool f=0;while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();if(f)x=-x;}
template <class T,class ...Args>
inline void read(T &tmp,Args &...tmps){read(tmp);read(tmps...);}
const int N = 805;
int a[N],b[N];
int n,k;
long long dp[N][N],ans[N];
signed main(){
    freopen("clash.in","r",stdin);
    freopen("clash.out","w",stdout);
    read(n,k);
    for(R int i=1;i<=n;++i)read(a[i],b[i]);
    memset(dp,-0x3f3f3f3f,sizeof(dp));
    for(R int len = 2;len <= n;len += 2)
        for(R int i=1;i+len-1<=n;++i){
            int j = i + len - 1;
            if(a[i] + a[j] <= k){
                if(len != 2)
                    dp[i][j] = max(dp[i][j],dp[i+1][j-1] + b[i] + b[j]);
                else dp[i][j] = b[i] + b[j];
            }
            for(R int k=i;k<j;k++){
                dp[i][j] = max(dp[i][j],dp[i][k] + dp[k+1][j]);
            }
            //ans1 = max(ans1,dp[i][j]);
        }
    //不能全合并
    for(R int i=2;i<=n;++i){
        for(R int j=0;j<i-1;++j)
            ans[i] = max(ans[i],ans[j] + dp[j+1][i]);
        ans[i] = max(ans[i-1],ans[i]);    
    }
    printf("%lld",ans[n]);
}

从思考到敲完花了一个小时多点，不过好在做出来了，ybtoj区间dp没白刷嘿嘿。