解ける問題探すのが苦労。

解けそうで解けない問題が一番時間くう

0191

#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
    int n,m;
    while (scanf("%d%d",&n,&m)) {
        if (!n&&!m) break;
        double grow[n][n], dp[m][n];
        for (int i=0; i<n; i++) for (int j=0; j<n; j++) scanf("%lf",&grow[i][j]);
        for (int i=0; i<n; i++) dp[0][i]=1.0;
        for (int i=1; i<m; i++) {
            for (int j=0; j<n; j++) {
                dp[i][j]=0.0;
                for (int k=0; k<n; k++) dp[i][j]=max(dp[i][j], dp[i-1][k]*grow[k][j]);
            }
        }
        double res=0.0;
        for (int i=0; i<n; i++) res=max(res, dp[m-1][i]);
        printf("%.2lf\n",res);
    }
}

0551

その他って単純なDPってこと？

#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
int main() {
    int n, l;
    scanf("%d%d",&n,&l);
    int ice[n],dp[n];
    pair<int, int> row[n];
    for (int i=0; i<n; i++) {
        scanf("%d",&ice[i]);
        row[i].first=ice[i];
        row[i].second=i;
    }
    sort(row, row+n);
    int res=0;
    for (int i=n-1; i>=0; i--) {
        int k=row[i].second, k1=row[i].second-1, k2=row[i].second+1;
        dp[k]=0;
        if (k1>=0&&ice[k1]==0) dp[k]=dp[k1];
        if (k2<n&&ice[k2]==0) dp[k]=max(dp[k], dp[k2]);
        dp[k]+=l-ice[k];
        ice[k]=0;
        res=max(res,dp[k]);
    }
    printf("%d\n",res);
}