워너비 연습 경기 7 B 쇼핑 dp

3351 단어 DP
사고방식: dp[i][j]는 i일째 j개의 사탕이 가장 적게 든다는 것을 나타낸다.% 60 데이터가 넘으면 RE일 수 있습니다. 그룹을 크게 만들면 MLE를 할 수 있기 때문에 매일 사는 사탕에 대해 n개의 사탕을 초과하지 않도록 최적화해야 합니다.접두사와 를 기록한 다음 유사한 배낭 방법으로 i-1일에서 i일을 미루다.
#include
#include 
#include 
#include 
using namespace std;
const int MAXN = 305;
int dp[MAXN][MAXN];
int a[MAXN][MAXN];
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            scanf("%d",&a[i][j]);
    for(int i=1;i<=n;++i)
        sort(*(a+i)+1,*(a+i)+m+1);
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
            a[i][j]=a[i][j-1]+a[i][j];
    }
    int k=2;
    memset(dp,0x3f,sizeof(dp));
    for(int i=1;i<=m;++i)
        dp[1][i]=a[1][i]+i*i;
    for(int i=2;i<=n;++i)
    {
        for(int j=i;j<=k*m;++j)
        {
            dp[i][j]=min(dp[i-1][j],dp[i][j]);

            for(int c=1;c<=m;++c)
            {
                if(j-c>=i-1)
                dp[i][j]=min(dp[i][j],dp[i-1][j-c]+c*c+a[i][c]);
            }
        }
        k++;
    }
    printf("%d
", dp[n][n]);
    return 0;
}
Zscript Zplugen 자신에게 적합한 요약 ①
GTB, LAMP 개발 기초의 자습 내용

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage