Usaco3.4 "broken Gong rock" band raucous rockers - DP

https://www.luogu.com.cn/problem/P2736
The question
Given $N（1\le N\le 20）$ song , Choose several songs from them , issue $M（1\le M\le 20）$ Zhang CD.
Each sheet CD At most $T（1\le T\le 20）$ Minutes of music , One song cannot be divided into two CD in .CD The quantity can be used up , It can also be done .

Choose according to the following criteria ：

1. Songs must be written in chronological order in all CD Appear on the disk .( notes ： The first $i$ The creation time of the last song of Zhang pan is earlier than that of $i+1$ The first song of the disc )
2. Select as many songs as possible .

ask , Can be installed $M$ Zhang CD The maximum number of songs ？

Ideas
“ Songs must be written in chronological order in all CD Appear on the disk ” This condition shows that you can't be greedy directly .
Consider using dp, The maximum number of songs that can be stored in the current capacity is transferred from the capacity minus the current song size .
and “ One song cannot be divided into two CD in ” This condition indicates that you cannot simply transfer from the previous capacity , We also need to consider whether to pack it in two pieces .

therefore , Define the State f[i, j, k] Express , For the former i A song , Before use j Zhang CD Plus k minute , The maximum number of songs that can be accommodated .
Then the final state is f[n, m, 0].

State shift ：

• First, inherit the state of the previous position ：f[i, j, k] = f[i-1, j, k];
• When additional k Minutes is greater than the current song size , You can start from f[i-1, j, k-a[i] To transfer ：f[i, j, k] = f[i-1, j, k-a[i]] + 1;
• otherwise , It needs to be stored in the previous record , from f[i-1, j-1, t-a[i]] To transfer ：f[i, j, k] = f[i-1, j-1, t-a[i]] + 1;

Code

#include<bits/stdc++.h>
using namespace std;

const int N = 210, mod = 1e9+7;
int T, n, m;
int a[N];
int f[N][N][N];

signed main(){
    
	int t;
	cin >> n >> t >> m;
	for(int i=1;i<=n;i++) cin >> a[i];
	
	for(int i=1;i<=n;i++){
    
		for(int j=0;j<=m;j++){
    
			for(int k=0;k<=t;k++)
			{
    
				f[i][j][k] = f[i-1][j][k];
				if(k>=a[i]) f[i][j][k] = max(f[i][j][k], f[i-1][j][k-a[i]] + 1); 
				else if(t-a[i] >= 0 && j >= 1) f[i][j][k] = max(f[i][j][k], f[i-1][j-1][t-a[i]] + 1);
			}
		}
	}
	cout << f[n][m][0];
	
	return 0;
}

Experience
State definition should dare to think .