2005NOIP 采药简单DP
#include<stdio.h>
#include<string.h>
![](/Images/OutliningIndicators/None.gif)
int t, n;
int time[101], v[101];
int f[101][1001];
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/None.gif)
void DP()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
int i, j;
for(i=n-1;i>=0;i--)
for(j=0;j<=t;j++)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(j>=time[i])f[i][j] = f[i+1][j] > f[i+1][j-time[i]]+v[i] ? f[i+1][j] : f[i+1][j-time[i]]+v[i];
else
f[i][j]=f[i+1][j];
}
}
![](/Images/OutliningIndicators/None.gif)
int main()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
while(scanf("%d%d",&t,&n)==2)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
memset(f,0,sizeof(f));
int i;
for(i=0;i<n;i++)
scanf("%d%d",&time[i],&v[i]);
![](/Images/OutliningIndicators/InBlock.gif)
DP();
printf("%d\n",f[0][t]);
}
![](/Images/OutliningIndicators/InBlock.gif)
return 0;
}
原文地址:https://www.cnblogs.com/SQL/p/918717.html