cdoj 1131 男神的礼物 区间dp

点击打开链接

思路： 区间dp，类似于石子合并的问题，每次枚举合并的点就好了

代码：

#include <bits/stdc++.h>using namespace std;typedef long long ll;ll dp[105][105],sum[105];int main(){	int T; cin>>T;	while(T--){		int n; cin>>n;		memset(dp,0,sizeof(dp));		memset(sum,0,sizeof(sum));		for(int i=1; i<=n; i++){			int x; cin >> x;			sum[i] = sum[i-1]+x;		}		for(int ri=2; ri<=n; ri++){			for(int le=ri-1; le>=1; le--){				for(int j=le; j<=ri; j++){ // 每次枚举合并的点					ll t = ((sum[j]-sum[le-1])%100)*((sum[ri]-sum[j])%100);					if(dp[le][ri]==0)						dp[le][ri] = dp[le][j]+dp[j+1][ri]+t;					else						dp[le][ri] = min(dp[le][ri],dp[le][j]+dp[j+1][ri]+t);				}			}		}		cout << dp[1][n] << endl;	}}