# Hdu-6968 (DP, and DP)

2021-07-27 06:22:40

A casual article .（ It's actually a multi school single person A There are too few opportunities ）

Classmate Zhu doesn't like studying very much. He hasn't finished preparing for the exam . There are several review materials at this time , For a set of data , Just spend \(x\) One day can improve the course \(y\) branch .（ I also want this good thing ） Ask if you can be in \(t\) Complete the counter attack within days, making the number of failed courses less than \(p\), If you can create miracles , Output the maximum score you can get .

First of all, we need to deal with \(m\) A review of , use DP To achieve , use \(f[i][j]\) It means the first one \(i\) The course got \(j\) The minimum number of days required for a score , This part of the state transition equation is more common , The complexity is \(O(m*100)\).

Then process whether the maximum score and the number of failed courses can be less than the target value . Still use DP To achieve , Use in code \(dp[i][j][k]\) Express \(i-1\) The course cost \(j\) Days and the number of failed courses is \(k\) The highest score you can achieve at . The equation of state transfer is \(dp[i+1][j+f[i][l]][k+1]=max(dp[i+1][j+f[i][l]][k+1],dp[i][j][k]+l)\).\(l\) It means the first one \(i\) Course acquisition \(l\) branch . This part makes a quadruple cycle DP, But because the coefficient is small （50*500*4*100）, Time complexity is no problem .

```#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define ll long long
#define pb push_back
using namespace std;
const int maxn = 60;
const int maxm = 15010;
string c[maxn];
int f[maxn][110];
map<string,int> mp;
int dp[maxn][510][4];
int main()
{
fast;
int T;
cin>>T;
while(T--)
{
mp.clear();
int n,m;
string s;
int x,y;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>c[i];
mp[c[i]]=i;
for(int j=0;j<=100;j++)
{
if(j==0) f[i][j]=0;
else f[i][j]=-1;
}
}
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>s>>x>>y;
int tmp=mp[s];
for(int j=100;j>=0;j--)
{
if(f[tmp][j]!=-1)
{
if(f[tmp][min(j+x,100)]==-1) f[tmp][min(j+x,100)] = f[tmp][j]+y;
else f[tmp][min(j+x,100)] = min(f[tmp][min(j+x,100)],f[tmp][j]+y);
}
}
}
int day,limit;
cin>>day>>limit;
int minn=1e9;
int maxx=-1;
int sum=0;
int flag=0;
for(int i=0;i<=n+1;i++)
{
for(int j=0;j<=day;j++)
{
for(int k=0;k<=limit;k++)
{
dp[i][j][k]=-1;
}
}
}
dp[1][0][0]=0;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=day;j++)
{
for(int k=0;k<=3;k++)
{
// if(k!=3) dp[i+1][j][k+1]=max(dp[i+1][j][k+1],dp[i][j][k]);
for(int l=0;l<=100;l++)
{
if(j+f[i][l]<=day && f[i][l]!=-1 && dp[i][j][k]!=-1)
{
if(l>=60) dp[i+1][j+f[i][l]][k]=max(dp[i+1][j+f[i][l]][k],dp[i][j][k]+l);
else
{
if(k!=3) dp[i+1][j+f[i][l]][k+1]=max(dp[i+1][j+f[i][l]][k+1],dp[i][j][k]+l);
}
}
}
}
}
}
/*for(int i=2;i<=n+1;i++)
{
for(int j=0;j<=day;j++)
{
for(int k=0;k<=limit;k++)
{
cout<<i<<' '<<j<<' '<<k<<' '<<dp[i][j][k]<<'\n';
}
}
}*/
for(int i=0;i<=day;i++)
{
for(int j=0;j<=limit;j++)
{
maxx=max(dp[n+1][i][j],maxx);
}
}
if(maxx!=-1) cout<<maxx<<'\n';
else cout<<"-1\n";
}
}```

https://chowdera.com/2021/07/20210722214741133l.html