沈阳2019icpc

港控/mmm° 2023-08-17 16:25 106阅读 0赞

【K题】Guanguan's Happy water

题意：其实就是求当前节点的前k个的期望值

对n分两种情况：

1.n<=k-----直接就加到a\[1...n\]

2.n>k----ans=suma+f\[k+1...n\]

最需要注意的是里面的数据类型：非常需要注意，能取模的尽量都取模

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=77;
    const ll mod=1e9+7;
    ll a[maxn],f[maxn];
    int main()
    {
        int t;
        scanf("%d",&t);
        int k;
        ll n;
        while(t--){
            scanf("%d%lld",&k,&n);
            ll suma=0,sumf=0;
            for(int i=1;i<=k;i++){
                scanf("%lld",&a[i]);
                suma=(suma+a[i])%mod;
            }
            for(int i=1;i<=k;i++){
                scanf("%lld",&f[i]);
                sumf=(sumf+f[i])%mod;
            }
            ll ans=0;
            if(n<=k){
                for(int i=1;i<=(int)n;i++)
                ans=(ans+a[i])%mod;
            }
            else{
                ans=suma%mod;            
                ll cnt=(n-k)/k;
                int len=n-cnt*k-k;
                cnt%=mod;
                ans=(cnt*sumf+ans)%mod;
                 for(int i=1;i<=len;++i)
                    ans=(ans+f[i])%mod;
            }
            printf("%lld\n",ans%mod);
        }
    }

//#pragma GCC optimize(2)
    
    #include <bits/stdc++.h>
    using namespace std;
    #define _ 0
    #define MX 100050
    #define pb push_back
    #define len length()
    #define IO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    
    typedef long long ll;
    typedef pair <int,int> iip;
    int i, j, cnt = 0;
    
    ll dp[MX];
    
    int main()
    {
    //    IO
        int n, m;
        while(scanf("%d%d", &n, &m) != EOF)
        {
            dp[0] = 0;
            for(int i = 1; i <= m+10000; i++)
            {
                dp[i] = 0x1f1f1f1f1f1f1f1f;
            }
            for(int k = 0; k < n; k++)
            {
                ll p, c;
                scanf("%lld%lld", &p, &c);
                for(int i = c; i <= m+10000; i++)
                {
                    dp[i] = min(dp[i-c]+p, dp[i]);
                }
            }
            ll a = 0x1f1f1f1f1f1f1f1f, b = m;
            for(int i = m; i <= m+10000; i++)
            {
                if(dp[i] <= a) a = dp[i], b = i;
            }
            printf("%lld %lld\n", a, b);
        }
    
        return ~~(0^_^0);
    }

转载于:https://www.cnblogs.com/Aiahtwo/p/11519965.html