【DP】模型：旅行商简化版

最基本的模板，直接上代码

#include 
#define inf (double)1e18+7
#define ll long long
using namespace std;
const ll maxn=1005;
template <typename t>void read(t &x)
{ll f=1;x=0;char ch=getchar();while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}x=x*f;
}
struct NODE
{ll x,y;
}node[maxn];
ll n,b1,b2;
double dp[maxn][maxn];double dis(ll a,ll b)
{return sqrt((node[a].x-node[b].x)*(node[a].x-node[b].x)+(node[a].y-node[b].y)*(node[a].y-node[b].y));
}bool cmp(NODE a,NODE b)
{return a.x<b.x;
}void init()
{freopen("B.in","r",stdin);
}void readdata()
{read(n);for(ll i=1;i<=n;i++){read(node[i].x),read(node[i].y);}
}void work()
{sort(node+1,node+n+1,cmp);for(ll i=1;i<=n;i++){for(ll j=1;j<=n;j++){dp[i][j]=inf;}}dp[1][1]=0;for(ll i=1;i<=n;i++){for(ll j=1;j<=n;j++){if(i!=j || i==1){ll k=max(i,j)+1;if(k==n+1){				if(i==n)dp[n][n]=min(dp[n][n],dp[n][j]+dis(j,n));if(j==n)dp[n][n]=min(dp[n][n],dp[i][n]+dis(i,n));}else {											dp[i][k]=min(dp[i][k],dp[i][j]+dis(j,k));dp[k][j]=min(dp[k][j],dp[i][j]+dis(i,k));}}}}printf("%.2lf",dp[n][n]);
}int main()
{
//	init();readdata();work();return 0;
}

DFS爆搜

#include 
using namespace std;
const int maxn=55;
int a[maxn][maxn];
int n,m;
int dp[maxn][maxn][maxn][maxn];
void init()
{
//	freopen("T2.in","r",stdin);
}void readdata()
{scanf("%d%d",&m,&n);for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)scanf("%d",&a[i][j]);memset(dp,-1,sizeof(dp));
}int dfs(int stax,int stay,int endx,int endy)
{if(stax>m+1||stax<0||stay>n+1||stay<0)return 0;if(endx>m+1||endx<0||endy>n+1||endy<0)return 0;if (stax==endx&&stay==endy)return 0;//judge if(dp[stax][stay][endx][endy]!=-1)	return dp[stax][stay][endx][endy];// memeryint max1=max(dfs(stax+1,stay,endx+1,endy),dfs(stax+1,stay,endx,endy+1));int max2=max(dfs(stax,stay+1,endx+1,endy),dfs(stax,stay+1,endx,endy+1));int ans=max(max1,max2)+a[stax][stay]+a[endx][endy];dp[stax][stay][endx][endy]=ans;return ans;
}void work()
{printf("%d",dfs(2,1,1,2));
}int main()
{
//	init();readdata();work();return 0;
}

少时诵诗书，吾问无为谓。
屦及剑及加，单打独斗大。