Codeforces Round #783

题意：给定一个n行m列的网格，你需要从起点（1，1），到达终点（n，m)。你可以向上下左右四个方向移动。不能在同一个方向上连续移动两次。求到达终点的最小的移动次数。

思路：令ma=max(n,m)，mi=min(n,m),可以先到达（mi,mi),再到达（n,m)。

参考代码：

#include
using namespace std;
const int N=1e6+10;
typedef long long ll;
int T=1;

void solve(){
    int a, b;cin>>a>>b;
    int mi=min(a,b);
    int ma=max(a,b);
    if(a==1 && b==1)cout<<"0"<<"\n";
    else if((a==1 && b==2) || (b==1 && a==2))cout<<1<<"\n";
    else if(a>=2 && b>=2){
        int ans=(mi-1)*2;
        ans+=2*(ma-mi);
        if((ma-mi)%2==1)ans--;
        cout<>T;
    while(T--){
        solve();
    }
    return 0;
}

题意：给定n个人和m个椅子（椅子排列成一个圆圈），一个长度为n的数组a， a i a_i ai​表示第i个人的左右两边至少有 a i a_i ai​个空的椅子。问是否能在给定的要求下让所有人都坐下来。

思路：对数组进行从小到大排序，先安排第n个人坐下，然后是第n-1个人，依次类推。这样可以使得空椅子的利用率最大。

参考代码：

#include
using namespace std;
const int N=1e6+10;
typedef long long ll;
int T=1;
int a[N];

void solve(){
    int n, m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    ll ans=n;int f=0;
    sort(a+1,a+1+n);
    ans+=a[n];
    for(int i=n;i>=2;i--){
        ans+=a[i];
        if(ans>m){
            f=1;break;
        }
    }
    if(ans<=m && f==0)cout<<"YES"<<"\n";
    else cout<<"NO"<<"\n";
}

int main(){
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

题意：给定数组a和数组b，数组b的储值为0。有两种 *** 作: b i − a i b_i - a_i bi​−ai​ 和 b i + a i b_i+a_i bi​+ai​。问最少需要 *** 作多少次，使数组b从一个全零的数组变成一个严格单调递增的数组。

思路：观察可知，最后得到的数组b，一定存在一个零。由数据范围可知，可以直接暴力枚举零的位置。

参考代码：

#include
using namespace std;
const int N=5010;
typedef long long ll;
int T=1;
ll a[N];

void solve(){
    int n;cin>>n;
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    ll res=1e18;
    for(int i=1;i<=n;i++){
        ll ans=0;
        int cnt=i;ll f=0;
        for(int j=i-1;j>=1;j--){
            ll x=f/a[j]+1;
            ans+=x;
            f=x*a[j];
        }
        f=0;
        for(int j=i+1;j<=n;j++){
            ll y=f/a[j]+1;
            ans+=y;
            f=y*a[j];
        }
        res=min(res,ans);
    }
    cout<>T;
    while(T--){
        solve();
    }
    return 0;
}

题意：把一个数组分成很多段，每一段的和如果为正数，那么这一段的价值就是长度的正值 ，如果这一段的和为负数，那么这一段的价值就是长度的正值。求这个数值划分成几段之后，价值的最大值。

思路：数据结构优化dp
暴力dp：

// for(int i=1;i<=n;i++){
//         f[i]=-1e9;
//         for(int j=0;js[j]){
//                 f[i]=max(f[i],f[j]+i-j);
//             }else if(s[i]==s[j]){
//                 f[i]=max(f[i],f[j]+0);
//             }else if(s[i]