暴力计算

//本来想写DP,写着写着成了暴力,= =
//因为和最大为450,直接暴力求出所有可能的和的个数,最后计算和为3的倍数的个数和,即可。。。
#include<bits/stdc++.h>
using namespace std;

#define ffor(i, a, b) for(int i = (a); i<(b); i++)
typedef long long ll;
const int MOD=1e9+7;
const int maxn=460;
ll a[55], d[450], len, sum;

void Read(){
    char c = getchar();
    while(isdigit(c)){
        a[++len] = c-'0' , c=getchar();
        sum+=a[len];
    }
}

int main(){
    Read();

    d[a[1]]++;
    for(int i=2; i<=len; i++){
        for(int j=sum; j>=a[i]; j--){
            if(d[j-a[i]] > 0) d[j]+=d[j-a[i]];
        }
        d[a[i]]++;
    }
    ll ans= 0;
    for(int i=0; i<=sum; i+=3){
        ans = (ans+d[i])%MOD;
    }
    cout <<ans;
    return 0;
}

全部评论
6666 这方法可以   变成背包问题了
点赞 回复 分享
发布于 2020-02-11 11:41

相关推荐

07-11 11:15
中南大学 Java
好可爱的hr姐姐哈哈哈哈
黑皮白袜臭脚体育生:兄弟们貂蝉在一起,吕布开了
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务