1 条题解

  • 0
    @ 2023-3-5 15:36:36

    仅仅多了一维而已(+一个小优化) 好好看看01背包一级一维背包就行了

    #include<bits/stdc++.h>
    using namespace std;
    int n,O,N;
    int dp[101][101];
    int o2[1010],n2[1010],w[1001];
    int main()
    {
        scanf("%d%d%d",&O,&N,&n);
        for(int i=1;i<=n;i++)
    	{
    		scanf("%d%d%d",&o2[i],&n2[i],&w[i]);
    	}
    	memset(dp,127,sizeof(dp));
    	dp[0][0]=0;
       	for(int i=1;i<=n;i++)
        {
            for(int j=O;j>=0;j--)
            {
            	for(int k=N;k>=0;k--)
    	        {
            	    int t1=j+o2[i],t2=k+n2[i];
            	    if(t1>O) t1=O;
            	    if(t2>N) t2=N;
            	    dp[t1][t2]=min(dp[t1][t2],dp[j][k]+w[i]);//优化
           		}
    		}
            
        }
        printf("%d",dp[O][N]);
        return 0; 
    }
    
    • 1

    信息

    ID
    467
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    递交数
    19
    已通过
    7
    上传者