牛客算法周周练8

A.小A买彩票

Solution

1. DP
   表示第次摸奖能摸到的次数， (表示本次摸到的奖)
   这个好像不能优化空间，改成滚动数组。

2. 记忆化搜索

3. 组合数学

   Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 1e6 + 5;

int n;
ll f[35][200];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    f[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=4*i;j>0;j--)
            for(int k=1;k<=4;k++)
                if(j-k>=0)
                    f[i][j]+=f[i-1][j-k];
    ll cnt=0,tot=0;
    for(int i=n;i<=4*n;i++)
        if(i>=3*n)
            cnt+=f[n][i];
        else
            tot+=f[n][i];
    ll sum=cnt+tot;
    cout<<cnt/__gcd(cnt,sum)<<"/"<<sum/__gcd(cnt,sum)<<'\n';
    return 0;
}

B.「金」点石成金

Solution

的范围很小，DFS选和不选即可。

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 15 + 5;

int n;
ll a[N],b[N],c[N],d[N];
ll ans=NINF;

void dfs(int x,ll u,ll v){
    if(x==n){
        ans=max(ans,1ll*u*v);
        return;
    }
    int tx=x+1;
    dfs(tx,u+a[tx],(v>b[tx]?v-b[tx]:0));
    dfs(tx,(u>d[tx]?u-d[tx]:0),v+c[tx]);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i]>>b[i]>>c[i]>>d[i];
    dfs(0,0,0);
    cout<<ans;
    return 0;
}

E.

Solution

所在点为

1. 记录行的最小值并减掉 (算最小值时跳过所在点，操作时不跳过)
2. 记录列的最小值并减掉 (算最小值时跳过所在点，操作时不跳过)
3. 

   Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 1e3 + 5;

int n,sx,sy;
ll a[N][N],r[N],c[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
            if(a[i][j]==-1){
                sx=i,sy=j;
            }
        }
    }
    for(int i=1;i<=n;i++) r[i]=c[i]=INF;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==sx && j==sy) continue;
            r[i]=min(r[i],a[i][j]);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            a[i][j]-=r[i];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==sx && j==sy) continue;
            c[j]=min(c[j],a[i][j]);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            a[i][j]-=c[j];
        }
    }
    cout<<-1-a[sx][sy]<<'\n';
    return 0;
}