题解 P1566 【加等式】

· · 题解

本题难度不大，想到就好打
类似背包吧
就是相当于求一个数用集合内的数的和表示有多少表示方法
注意的是3=3不算加等式 

#include<bits/stdc++.h>
using namespace std;
int ji[30050],yh[2000];//ji为数的表示过程数组
int main()
{
    int n,m,he=0,ans=0;
    cin>>n;//数据组数
    for(int i=1;i<=n;i++)
    {
        cin>>m;//小数据数量
        he=0;//一定记得，初始化
        memset(yh,0,sizeof(yh));//初始化，同上
        memset(ji,0,sizeof(ji));//同上
        for(int j=1;j<=m;j++)
        {
            cin>>yh[j];//输入
            he=max(he,yh[j]);  
            //he为集合内最大值，同样，也就是上界
        }
        ji[0]=1;//一定记得，类似题都要有这句
        for(int j=1;j<=m;j++)
        {
            for(int q=he;q>=yh[j];q--)
            {
                ji[q]=ji[q-yh[j]]+ji[q];  
 //计算过程，就是算到A的方法为A本身方法+A-c方法（A>c
            }
        }
        ans=0;
        for(int j=1;j<=m;j++)
        {
            ans=ans+ji[yh[j]];  
            //累加过程，注意不能写ji[yh[j]]
        }
        ans=ans-m;//3=3不算加等式
        cout<<ans<<endl;
    }
    return 0;//一定记得（我没一等的原因，还好还有一次机会%%%%%）
}

两年OI一场空，不打回归（return 0）见祖宗