2022绵阳+dp经典问题

J. Middle Race

构造方程:y=a*x+b*y+c*z,使得你获得的分数y尽可能地逼近整个游戏总分的均值。
这一点我是想到的！！！为什么没立刻反应到？
对于参数a值进行1~n的枚举；参数b进行二分；参数c便用n去减。

#pragma-GCC-optimize("-Ofast");
#include 
#define endl '\n'
#define int long long
#define ios ios::sync_with_stdio(false)

using namespace std;
const int N =2e5+5;
const int inf=1e18;
const int mod=1e9+7;
const double eps=1e-8;
int n,a,b,c,sa,sb,sc,dis,tar;

void solve()
{
    cin>>n>>a>>b>>c;
    a=a*3;b=b*3;c=c*3;
    if(a>b) swap(a,b);if(a>c) swap(a,c);if(b>c) swap(b,c);
    tar=(a+b+c)*n/3;
    dis=tar-n*a;
    for(int i=0;i<n;i++)
    {
        int l=0,r=n-i,mid,ans;
        while(l<=r)
        {
            mid=(l+r)/2;
            int tmp=i*a+mid*b+(n-i-mid)*c;
            if(tmp>=tar)
            {
                l=mid+1;
                if(tmp-tar<dis) dis=tmp-tar,sa=i,sb=mid,sc=n-i-mid;
            }
            else
            {
                r=mid-1;
                if(tar-tmp<dis) dis=tar-tmp,sa=i,sb=mid,sc=n-i-mid;
            }
        }

    }
    for(int i=1;i<=n;i++)
    {
        if(i<=sa)
            cout<<a/3<<endl;
        else if(i<=sa+sb)
            cout<<b/3<<endl;
        else
            cout<<c/3<<endl;
        fflush(stdout);
        int y,z;
        cin>>y>>z;
    }

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



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

G. Let Them Eat Cake

一个签到题。如果使用vector的删除操作会比较麻烦，用两个vector不断更新来回赋值也可做到筛选的操作。

#include 
#define endl '\n'
#define int long long
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))

using namespace std;
const int N =2e5+5;
const int inf=1e18;
const int mod=1e9+7;
const double eps=1e-8;
int n;

void solve()
{
    vector<int>a,b;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;cin>>x;
        b.push_back(x);
    }
    int ans=0;
    while(1)
    {
        if(b.size()<=1) break;
        for(int x:b) a.push_back(x);
//        for(int x:a)
//            cout<
//        cout<
        b.clear();
        for(int i=0;i<a.size();i++)
        {
            if(i==0&&a[i]>a[i+1])
                b.push_back(a[i]);
            else if(i==a.size()-1&&a[i]>a[i-1])
                b.push_back(a[i]);
            else if(a[i]>a[i-1]&&a[i]>a[i+1])
                b.push_back(a[i]);
        }
        a.clear();
        ans++;
    }
    cout<<ans<<endl;
}
signed main()
{
    ios;
//    int T;cin>>T;
//    while(T--)
        solve();
    return 0;
}



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

1.矩阵连乘，求最小计算次数

#include 
#define endl '\n'
#define int long long
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))

using namespace std;
const int N =2e5+5;
const int inf=1e18;
const int mod=1e9+7;
const double eps=1e-8;
int n,row[1005],col[1005],p[1005],s[1005][1005],dp[1005][1005];
void dfs(int i,int j)
{
    if(i==j)
    {
        cout<<"A"<<i;
        return;
    }
    cout<<"(";
    dfs(i,s[i][j]);
    dfs(s[i][j]+1,j);
    cout<<")";
}
void solve()
{
    cin>>n;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++) dp[i][j]=inf;
    for(int i=1;i<=n;i++)
        dp[i][i]=0;
    for(int i=1;i<=n;i++) cin>>row[i]>>col[i];
    p[0]=row[1];
    for(int i=1;i<=n;i++)
        p[i]=col[i];
    for(int len=2;len<=n;len++)
    {
        for(int i=1;i<=n-len+1;i++)
        {
            int j=i+len-1;
            dp[i][j]=dp[i+1][j]+p[i-1]*p[i]*p[j];
            s[i][j]=i;
            for(int k=i+1;k<j;k++)
            {
                int tmp=dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j];
                if(tmp<dp[i][j])
                {
                    dp[i][j]=tmp;
                    s[i][j]=k;
                }
            }
        }
    }
    cout<<dp[1][n]<<endl;
    dfs(1,n);
}
signed main()
{
    ios;
    solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

备忘录方法实现：自顶向下

#include 
#define endl '\n'
#define int long long
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))

using namespace std;
const int N =2e5+5;
const int inf=1e18;
const int mod=1e9+7;
const double eps=1e-8;
int n,row[1005],col[1005],p[1005],s[1005][1005],dp[1005][1005];
void print(int i,int j)
{
    if(i==j)
    {
        cout<<"A"<<i;
        return;
    }
    cout<<"(";
    print(i,s[i][j]);
    print(s[i][j]+1,j);
    cout<<")";
}
int dfs(int l,int r)
{
    if(dp[l][r]!=-1) return dp[l][r];
    if(l==r) return 0;
    int tmp=dfs(l,l)+dfs(l+1,r)+p[l-1]*p[l]*p[r];
    s[l][r]=l;
    for(int k=l+1;k<r;k++)
    {
        int res=dfs(l,k)+dfs(k+1,r)+p[l-1]*p[k]*p[r];
        if(res<tmp)
            tmp=res,s[l][r]=k;
    }
    return dp[l][r]=tmp;
}
void solve()
{
    cin>>n;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++) dp[i][j]=-1;
    for(int i=1;i<=n;i++)
        dp[i][i]=0;
    for(int i=1;i<=n;i++) cin>>row[i]>>col[i];
    p[0]=row[1];
    for(int i=1;i<=n;i++)
        p[i]=col[i];
    cout<<dfs(1,n)<<endl;
    print(1,n);
}
signed main()
{
    ios;
    solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

最大字段和

O(n)复杂度

#include 
#define endl '\n'
#define int long long
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))

using namespace std;
const int N =2e5+5;
const int inf=1e18;
const int mod=1e9+7;
const double eps=1e-8;
int n,a[N];

void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int ans=0,sum=0,beg,l,r;
    for(int i=1;i<=n;i++)
    {
        if(sum>0) sum+=a[i];
        else
        {
            sum=a[i];
            beg=i;
        }
        if(sum>ans)
        {
            ans=sum;l=beg;r=i;
        }
    }
    cout<<l<<" "<<r<<" "<<ans<<endl;
}
signed main()
{
    ios;
    solve();
    return 0;
}



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41