【高频考点】动态规划

m0_57082284

215人浏览 · 2026-06-10 00:14:26

m0_57082284 · 2026-06-10 00:14:26 发布

2026年2月4日模型推理量化加速优化问题（通过率100%）

import sys
import numpy as np

def solve():
    data = sys.stdin.read().strip().split()
    L=int(data[0])
    T=float(data[1])
    W=int(round(T*100))

    p=2
    layers=[]
    for _ in range(L):
        K=int(data[p])
        p=p+1
        options=[]
        for _ in range(K):
            bit=data[p]
            p=p+1
            w=int(round(float(data[p])*100))
            p=p+1
            mem=float(data[p])
            p=p+1
            options.append((w,mem))
        layers.append(options)
        INF=float('inf')
    dp=np.full(W+1,INF,dtype=np.float64)
    dp[0]=0
    for options in layers:
        ndp=np.full(W+1,INF,dtype=np.float64)
        for w,mem in options:
            if w<=W:
                ndp[w:]=np.minimum(ndp[w:],dp[:W-w+1]+mem)
        dp=ndp
    ans=np.min(dp)
    print(f"{ans:.2f}")

if __name__=="__main__":
    solve()

2025年10月22日最大能量路径（通过率100%）

#include <iostream>
#include <vector>
//#include <algorithm>

using namespace std;

void solve() {
    
    int H, W, K;
    cin >> H >> W >> K>>K;
    
    int h = H + 2 * (K / 2);
    int w = W + 2 * (K / 2);
    
    vector<vector<int> > photo(h, vector<int>(w, 0));
    vector<vector<int> > value(H, vector<int>(W, 0));
    
    int start_h = K / 2;
    int start_w = K / 2;
    
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            int num;
            cin >> num;
            photo[start_h + i][start_w + j] = num;
        }
    }
    
    vector<vector<int> > filter_K(K, vector<int>(K, 0));
    for (int i = 0; i < K; i++) {
        for (int j = 0; j < K; j++) {
            cin >> filter_K[i][j];
        }
    }
    
    // 卷积计算
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            int sum = 0;
            for (int x = 0; x < K; x++) {
                for (int y = 0; y < K; y++) {
                    sum += photo[i + x][j + y] * filter_K[x][y];
                }
            }
            value[i][j] = sum;
        }
    }
    
    // 动态规划 - 关键修复
    vector<double> ans;
    
    for (int start_row = 0; start_row < H; start_row++) {
        vector<vector<double> > E(H, vector<double>(W, 0));
        E[start_row][0] = value[start_row][0];
        
        // 修复：先遍历列 v，再遍历行 u
        for (int v = 1; v < W; v++) {
            for (int u = 0; u < H; u++) {
                // 必须检查 E[u][v-1] 是否有效（不是 -1e18）
                double best = -1e18;
                
                
                best = max(best, E[u][v-1] + value[u][v]);
                
                // 从左上角来
                if (u-1 >= 0 ) {
                    best = max(best, E[u-1][v-1] + value[u][v]);
                }
                // 从左下角来
                if (u+1 < H) {
                    best = max(best, E[u+1][v-1] + value[u][v]);
                }
                
                E[u][v] = best;
                
            }
        }
        
        double last_col_max = 0;
        for (int u = 0; u < H; u++) {
            if (E[u][W-1] > last_col_max) {
                last_col_max = E[u][W-1];
            }
        }
        ans.push_back(last_col_max);
    }
    double result = 0;
    for(int i=0;i<ans.size();i++){
    	result=max(result,ans[i]);
	}
    printf("%.1f\n", result);
}

int main() {
    solve();
    return 0;
}

2025年9月17日大模型分词（90%）

#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;


void solve(){
	string text;
	cin>>text;
	int n;
	cin>>n;
	unordered_map<string, int> map;
	for(int i=0;i<n;i++){
		string a;
		int p;
		cin>>a>>p;
		map[a]=p;
	}
	int m;
	cin>>m;
	unordered_map<string, unordered_map<string,int> > tran_map;
	for(int i=0;i<m;i++){
		string a,b;
		unordered_map<string, int> sub_map;
		int x;
		cin>>a>>b>>x;
		sub_map[b]=x;
		tran_map[a]=sub_map;
	}
	vector<int> dp(text.size()+1,-1e9);
	dp[0]=0;
	vector<string> last(text.size()+1,"");
	for(int i=1;i<text.size()+1;i++){
		
		for(int j=0;j<i;j++){
			string sub_text=""; 
			for(int k=j;k<i;k++) sub_text+=text[k];
			int trans_score =0;
			if(map.find(sub_text)!=map.end()){
				if(j>0 && last[j]!=""){
					string last_token = last[j];
					if(tran_map.find(last_token)!= tran_map.end() && tran_map[last_token].find(sub_text)!= tran_map[last_token].end()){
						trans_score=tran_map[last_token][sub_text];
					}
				}
				if(dp[i]<dp[j]+map[sub_text]+trans_score){
					dp[i]=dp[j]+map[sub_text]+trans_score;
					last[i]=sub_text;	
				}
				
			}
		}
	}
	if(dp[text.size()]<-1e8)
		cout<<0<<endl;
	else
		cout<<dp[text.size()]<<endl;
	
}

int main(){
	solve();
	return 0;
}

2026年3月18日大模型训练显存优化算法（通过率30%）

#include<iostream>
#include<vector>
using namespace std;

void solve(){
    int m,n;
    cin>>m;
    cin>>n;
    vector<int> a(n),b(n),c(n);
    vector<int> v;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>b[i];
    for(int i=0;i<n;i++) cin>>c[i];
    for(int i=0;i<n;i++) v.push_back(min(b[i],c[i]));
    vector<vector<int> > dp(n, vector<int>(m+1,1e9));
    dp[0][0]=0;
    if(m>=a[0]) dp[0][a[0]]=v[0];
    
    for(int i=1;i<n;i++){
        for(int j=1;j<m+1;j++){
            if(j>=a[i])
                dp[i][j]=min(dp[i-1][j],dp[i-1][j-a[i]]+v[i]);
            else
                dp[i][j]=dp[i-1][j];
        }
    }
    if(dp[n-1][m]==1e9)
        cout<<"error"<<endl;
    else
        cout<<dp[n-1][m]<<endl;
}

int main(){
    solve();
    return 0;
}