1157.txt

来自「acm pku 1157题」· 文本 代码 · 共 28 行

转入正题,看当的一个课件,上面写什么变换为图啊,,然后优化啊什么的,,完全误导,只要定义q[i][j] 表示把前 i 束花放入前 j 个花瓶时得到的最大值,递推关系就相当明显了,如果 i 放在 j 里,则q[i][j]=q[i-1][j-1]+a[i][j],如果 i不放在 j,则q[i][j]=q[i][j-1],要注意下初始值.

代码如下:

#include <stdio.h>

int a[102][102];
int q[102][102];

int main(){
    int f,v;
    int lt,ll;
    
    scanf("%d %d",&f,&v);
    for(lt=1;lt<=f;lt++) for(ll=1;ll<=v;ll++) scanf("%d",&a[lt][ll]);
    q[0][0]=0;
    for(lt=1;lt<=f+1;lt++) q[lt][0]=-25000,q[0][lt]=0;
    for(lt=1;lt<=f;lt++){
        for(ll=lt;ll<=v-f+lt;ll++){
            if(q[lt][ll-1]>(q[lt-1][ll-1]+a[lt][ll]))
                q[lt][ll]=q[lt][ll-1];
            else
                q[lt][ll]=q[lt-1][ll-1]+a[lt][ll];
        }
    }
    printf("%d\n",q[f][v]);
}