ACW1049

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N =10010;

int n,T;
int home[N];

int dfs(int x){
    if(x>n-1) return 0;
    else return max(dfs(x+1),dfs(x+2)+home[x]);

}

int main(){
    cin>>T;
    while(T--){
        cin>>n;
        for(int i =-;i<n;i++){
            cin>>home[i];
        }
        int res=dfs(0);
        cout<<res<<endl;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
home=[0 for x in range(0,10010)]

def dfs(x):
    if(x>n-1):
        return 0
    else:
        return max(dfs(x+1),dfs(x+2)+home[x])


T=eval(input())
while(T>=0):
    T-=1
    n=eval(input())
    home = list(map(int, input().split()))
    res=dfs(0)
    print(res)

P1216

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N=10010;
int n;
int g[N][N];
int f[N][N];


int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++)
        cin>>g[i][j];
    }
    for(int i=n;i>=1;i--){
        for(int j=1;j<=n;j++){
            f[i][j]=max(f[i+1][j],f[i+1][j+1])+g[i][j];
        }
    }
    cout<<f[1][1]<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
g=[[0]*1010 for _ in range(1010)]
f=[[0]*1010 for _ in range(1010)]
n=int(input())
for i in range(1,n+1):  
    ls = list(map(int,input().split()))
    for j in range(1,i+1):
        g[i][j]=ls[j-1]

for i in range(n,0,-1):
    for j in range(1,i+1):
        f[i][j]=max(f[i+1][j],f[i+1][j+1])+g[i][j]
    
print(f[1][1])

ACW2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
int n,m;
const int N=1010;
int v[N];
int w[N];
int f[N][N];

int main(){
    cin>>n>>m;
    for(int i=1;1<=1;i++){
        cin>>v[i]>>w[i];
    }
    for(int i=n;i>=1;i--){
        for(int j=0;j<=m;j++){
            if(j<v[i]) f[i][j]=f[i+1][j];
            else{
                f[i][j]=max(f[i+1][j],f[i+1][j-v[i]]+w[i]);
            }
        }
    }
    cout<<f[1][m]<<endl;
    return 0;
}

ACW3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
V=[00 for _ in range(1010)]
W=[00 for _ in range(1010)]
f=[[0]*1010 for _ in range(1010)]
n,v=map(int,input().split())
for i in range(1,n+1):
    ls=list(map(int,input().split()))
    V[i]=ls[0]
    W[i]=ls[1]
for i in range(n,0,-1):
    for j in range(0,v+1):
        if(j<V[i]):
            f[i][j]=f[i+1][j]
        else:
            f[i][j]=max(f[i+1][j],f[i][j-V[i]]+W[i])
print(f[1][v])

ACW8

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N=1010;
int n,v,m;
int v[N],w[110],m[110];

int dfs(int x,int spV, int spM){
    if(x>n) return 0;
    else{
        if(spV>=v[x] && spM>=m[x]){
        if(mem[x][spV][spM]) return mem[x][spV][spM];
        else{
            mem[x][spV][spM]=max(dfs(x+1,spV,spM),dfs(x+1,spV-v[x],spM-m[x])+w[x]);
        }
        }
        else{
            return dfs(x+1,spV,spM);
        }
    }
}

int main(){
    cin>>n>>v>>m;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>m[i]>>w[i];
    }
    int res=dfs(1,v,m);
    cout<<res<<endl;
    return 0;
}