2944. 四元一次方程

枚举就完事了

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    for(int i=0;i<t;i++)
    {
        int n,g=0;
        cin>>n;
        for(int w=0;w<=n/4;w++)
            for(int x=0;x<=n/3;x++)
                for(int y=0;y<=n/2;y++)

        {
            if(4*w+3*x+2*y<=n)
                g++;
        }
        cout<<g<<endl;
    }
    return 0;
}

用的完全背包，结果发现枚举可以过就离谱了

DP

此题四重循环直接枚举即可
但是1000^4>10^8
会超时，因此需要优化一下

include

using namespace std;
int T,n;
void solve()
{
int ret=0;
for(int w=0;w<=n;w++)
for(int x=0;x<=n;x++)
{
if(w+x>n) break;
for(int y=0;y<=n;y++)
{
int z=n-(4w+3x+2*y);
if(z<0) break;
if(z>=0) ret++;
}
}

cout<<ret<>T;
for(int step=0;step>n;
solve();
}
}

首先z是可以通过w,x,y,n算出来的，因此z不需要枚举。
其次，w+x已经大于n的时候，就不用枚举w和x不变，y更大的情况了，也不用枚举w不变的时候，x更大的情况。
w+x+y已经大于n的时候，之后，w和x不变，y更大的情况也不用枚举了

include

include

using namespace std;
vector ans(1001, 0);
int main() {
ans[0] = 1;
for (int i = 1; i <= 4; ++i) {
for (int j = i; j <= 1000; ++j) {
ans[j] += ans[j - i];
}
}
int n;
cin >> n;
while (n–) {
int temp;
cin >> temp;
cout << ans[temp] << endl;
}
}